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

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^971097取模。输入格式输入第一行为两个整数N , K N,KN,K。接下来的N NN行每行K KK个字符串为球员的姓氏保证第i ii行的字符串长度为i ii。输出格式输出一行一个整数为最多分出的队伍支数答案对10 9 7 10^971097取模。输入输出样例 #1输入 #13 2 a b ab bd abc abd输出 #15输入输出样例 #2输入 #23 3 a b c aa ab ac aaa aab aca输出 #26输入输出样例 #3输入 #33 1 a bc def输出 #30说明/提示样例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≤501 ≤ K ≤ 1500 1\leq K\leq 15001≤K≤1500。任务编号特殊限制分值0 00为样例0 001 11N 5 , K 10 N5,K10N5,K1020 20202 22N 50 , K 100 N50,K100N50,K10030 30303 33无特殊限制。50 5050C实现#includebits/stdc.h#defineintlonglong#definepbpush_back#defineP1145141#defineULLunsignedlonglongusingnamespacestd;constintN51,K1600,mod1e97;intn,k;intsum;intans[N][K];vectorintG[K];ULL dt[N][K][3];ULLHash(chars[],inti,intlen){ULL res0;for(;ilen;i)resres*Ps[i]-a1;returnres;}signedmain(){chara[K];cinnk;for(inti1;ik;i){cina;dt[1][i][2]Hash(a,0,strlen(a));}for(inti1;ik;i)ans[1][i]1;for(inti2;in;i){for(intj1;jk;j){cina;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(intt1;tk;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(intj1;jk;j)for(autot:G[j])ans[i][j]ans[i-1][t],ans[i][j]%mod;for(intj1;jk;j)G[j].clear();}for(inti1;ik;i)sumans[n][i],sum%mod;coutsumendl;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容