BestCoder Round #75 1003 - King's Order

时间：2021-02-26 12:36:53
国王演讲后士气大增，但此时战争还没有结束，国王时不时要下发命令。

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

此时将军找到了你，你需要告诉他，给定命令的长度长度为 n，有多少种不同的命令可以是国王发出的 。（也就是求长度为 n 的合格字符串的个数）当然，国王可能说出一句话没有犯任何口吃，就像他那次演讲一样。

为了简化答案，国王的命令中只含有小写英文字母，且对答案输出模 1000000007。

我们认为两个命令如果完全相同那么这两个字符串逐个比较就完全相同。
第一行一个整数表示测试组数：T(T≤10)T(T \le10)T(T≤10)。

每组数据占一行，每行一个正整数 n(n≤2000) 表示字符串的长度。


输出描述




共 T 行，每行一个整数表示合法的命令数量。




输入样例




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






 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 #define LL long long

 const int mod=;

 int t,n;

 LL dp[][][],ans;

 void fuc(){

     for(int i=;i<=;i++)dp[][i][]=;

     for(int i=;i<=;i++){

         for(int j=;j<=;j++){

             for(int k=;k<=;k++) if(j!=k) {

                 for(int p=;p<=;p++)

                 dp[i][j][]=(dp[i][j][]+dp[i-][k][p])%mod;

             }

             dp[i][j][]=dp[i-][j][];

             dp[i][j][]=dp[i-][j][];

         }

     }

 }

 int main(){

     memset(dp,,sizeof(dp));

     fuc();

     scanf("%d",&t);

     while(t--){

         scanf("%d",&n);

         ans=;

         for(int i=;i<=;i++){

             for(int j=;j<=;j++)

                 ans=(ans+dp[n][i][j])%mod;

         }

         printf("%lld\n",ans);

     }

 }






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遍即可




 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 #define LL long long

 const int mod=;

 int t,n;

 LL dp[][],ans;

 void fuc(){

     dp[][]=;

     for(int i=;i<=;i++){

             for(int k=;k<=;k++)

                 for(int p=;p<=;p++)

                     dp[i][]=(dp[i][]+dp[i-][p])%mod;

             dp[i][]=dp[i-][];

             dp[i][]=dp[i-][];

     }

 }

 int main(){

     memset(dp,,sizeof(dp));

     fuc();

     scanf("%d",&t);

     while(t--){

         scanf("%d",&n);

         ans=;

         for(int i=;i<=;i++)

             for(int j=;j<=;j++)

                 ans=(ans+dp[n][j])%mod;

         printf("%lld\n",ans);

     }

 }






相关文章