BestCoder Round #75 1003 - King's Order

国王演讲后士气大增，但此时战争还没有结束，国王时不时要下发命令。

由于国王的口吃并没有治愈，所以传令中可能出现：“让第三军-军-军，到前线去” 这样的命令。由于大洋国在军队中安插了间谍 ， 战事紧急，很多时候前线的指挥官不能分清哪些命令真正来自国王。但国王的命令有一个特点，他每次连续重复的字符最多

第一行一个整数表示测试组数： $\le10)T(T≤10)。 每组数据占一行，每行一个正整数 n(n≤2000) 表示字符串的长度。$

输出描述

共

输入样例

2
2
4

输出样例

676
456950

Hint

两个中没有不符合要求的，所以答案为  $26×26=67626\times 26 = 67626×26=676 四个不符合要求的只有 `aaaa` `bbbb` ... `zzzz`总共 26 个 那么答案就是： 264−26=45695026^4-26 = 45695026​4​​−26=456950$

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 #define LL long long
 6 const int mod=1000000007;
 7 int t,n;
 8 LL dp[2005][30][5],ans;
 9 void fuc(){
10     for(int i=1;i<=26;i++)dp[1][i][1]=1;
11     for(int i=2;i<=2000;i++){
12         for(int j=1;j<=26;j++){
13             for(int k=1;k<=26;k++) if(j!=k) {
14                 for(int p=1;p<=3;p++)
15                 dp[i][j][1]=(dp[i][j][1]+dp[i-1][k][p])%mod;
16             }
17             dp[i][j][2]=dp[i-1][j][1];
18             dp[i][j][3]=dp[i-1][j][2];
19         }
20     }
21 } 
22 int main(){
23     memset(dp,0,sizeof(dp));
24     fuc();
25     scanf("%d",&t);
26     while(t--){
27         scanf("%d",&n);
28         ans=0;
29         for(int i=1;i<=26;i++){
30             for(int j=1;j<=3;j++)
31                 ans=(ans+dp[n][i][j])%mod;
32         }
33         printf("%lld\n",ans);
34     }
35 }

d[i][j][k] 表示第i 位串，以字母 j 结尾，最后面连续字母有 k 个的数量。
d[i][j][2] 显然由 d[i-1][j][1] 即前一位串以 j 结尾只有一个连续的推得；
同理 d[i][j][3] 由的d[i-1][j][2] 推得
最后只有一个连续的 d[i][j][1] 显然只能由其余不同字母结尾的串推得 d[i-1][k][1]+d[i-1][k][2]+d[i-1][k][3] k!=j;

然后因为每个字母都是等效的，也就是不同的 j 的存放的数据相同。
那把可以中间的j 拿掉
d[i][k] k=2,k=3 依旧同理
k=1 时即为前一值乘25得，因为是前一位子串其余不同字母结尾 d[i][1]= sum of d[i-1][k]*25 1<=k<=3；
最后统计答案即循环 26遍即可

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 #define LL long long
 6 const int mod=1000000007;
 7 int t,n;
 8 LL dp[2005][5],ans;
 9 void fuc(){
10     dp[1][1]=1;
11     for(int i=2;i<=2000;i++){
12             for(int k=1;k<=25;k++)
13                 for(int p=1;p<=3;p++)
14                     dp[i][1]=(dp[i][1]+dp[i-1][p])%mod;
15             dp[i][2]=dp[i-1][1];
16             dp[i][3]=dp[i-1][2];
17     }
18 } 
19 int main(){
20     memset(dp,0,sizeof(dp));
21     fuc();
22     scanf("%d",&t);
23     while(t--){
24         scanf("%d",&n);
25         ans=0;
26         for(int i=1;i<=26;i++)
27             for(int j=1;j<=3;j++)
28                 ans=(ans+dp[n][j])%mod;
29         printf("%lld\n",ans);
30     }
31 }

秒客网

BestCoder Round #75 1003 - King's Order

相关文章