当前位置：首页 > news >正文

打卡信奥刷题（3005）用C++实现信奥题 P6221 [COCI 2019/2020 #6] Trener

news 2026/3/30 6:09:49

P6221 [COCI 2019/2020 #6] Trener

题目背景

题目翻译来自 LOJ3270。

题目描述

译自 COCI 2019/2020 Contest #6 T5.Trener

我们已经知道了学生们喜欢睡觉。Patrik 是这一记录的保持者。在最后一个梦中，他发现自己成为了他最喜欢的球队的队长。

为了参加一场比赛，他把自己的所有球员分为N NN组，每组K KK名球员，对于第i ii组的球员，他们的姓氏长度都为i ii。

现在，他要开始规划上场的球员组合了。一个组合有N NN名球员，并且组委会对上场的球队还有有以下要求：

所有球员的姓氏长度必须不同。
所有球员的姓氏必须为其他姓氏比他长一个字符的球员的连续子序列。

Patrik 想知道，自己最多能把这些球员分为多少支可以上场的队伍。答案对10 9 + 7 10^9+7109+7取模。

输入格式

输入第一行为两个整数N , K N,KN,K。

接下来的N NN行，每行K KK个字符串，为球员的姓氏，保证第i ii行的字符串长度为i ii。

输出格式

输出一行一个整数为最多分出的队伍支数，答案对10 9 + 7 10^9+7109+7取模。

输入输出样例 #1

输入 #1

3 2 a b ab bd abc abd

输出 #1

输入输出样例 #2

输入 #2

3 3 a b c aa ab ac aaa aab aca

输出 #2

输入输出样例 #3

输入 #3

3 1 a bc def

输出 #3

说明/提示

样例1 11说明：

可以分为如下队伍：

(a, ab, abc), (a, ab,abd), (b, ab, abc), (b, ab, abd), (b, bd, abd)。

数据范围：

对于100 % 100\%100%的数据，1 ≤ N ≤ 50 1\le N\le 501≤N≤50，1 ≤ K ≤ 1500 1\leq K\leq 15001≤K≤1500。

任务编号	特殊限制	分值
0 00	为样例	0 00
1 11	N = 5 , K = 10 N=5,K=10N=5,K=10	20 2020
2 22	N = 50 , K = 100 N=50,K=100N=50,K=100	30 3030
3 33	无特殊限制。	50 5050

C++实现

#include<bits/stdc++.h>#defineintlonglong#definepbpush_back#defineP1145141#defineULLunsignedlonglongusingnamespacestd;constintN=51,K=1600,mod=1e9+7;intn,k;intsum;intans[N][K];vector<int>G[K];ULL dt[N][K][3];ULLHash(chars[],inti,intlen){ULL res=0;for(;i<len;i++)res=res*P+s[i]-'a'+1;returnres;}signedmain(){chara[K];cin>>n>>k;for(inti=1;i<=k;i++){cin>>a;dt[1][i][2]=Hash(a,0,strlen(a));}for(inti=1;i<=k;i++)ans[1][i]=1;for(inti=2;i<=n;i++){for(intj=1;j<=k;j++){cin>>a;dt[i][j][0]=Hash(a,0,strlen(a)-1);dt[i][j][1]=Hash(a,1,strlen(a));dt[i][j][2]=Hash(a,0,strlen(a));for(intt=1;t<=k;t++)if(dt[i-1][t][2]==dt[i][j][0]||dt[i-1][t][2]==dt[i][j][1])G[j].pb(t);}for(intj=1;j<=k;j++)for(autot:G[j])ans[i][j]+=ans[i-1][t],ans[i][j]%=mod;for(intj=1;j<=k;j++)G[j].clear();}for(inti=1;i<=k;i++)sum+=ans[n][i],sum%=mod;cout<<sum<<endl;return0;}