题目描述愚蠢的小明觉得自己喜欢的条件太苛刻了很难找到合适的字符串现在对于某个字符串只要这个字符串子序列包含 “cn” 的他就喜欢。小明想让你求解长度在 n 以内能让小明喜欢的字符串有多少个 答案对 1097 取模。输入描述一个正整数n2≤n≤106输出描述一个正整数为满足条件的字符串数量对 1097 取模的值。输入输出样例输入2输出1(说明仅有“cn”这一个字符串合法)输入3输出77说明在长度为3的字符串里“c?n有26个”?cn有26个cn?有26个。但是,“cnn和ccn都重复计算量一次应该减去所以长度为3的字符串符合要求的共有26*3-276个。再加上长度为2的cn”所以长度不超过3且达到要求的字符串共有77个。数据规模对于测试点1n5对于测试点2n10对于测试点3n100解题思路这道题定义dp[i][j]为前iii个字符构造状态j的方案数。可以把状态拆分成以下三个状态0前iii个字符串没有出现过c(可以有n这样也不会构成cncncn)记为dp[i][0]dp[i][0]dp[i][0]状态1前iii个字符串出现了c但没出现n记为dp[i][1]dp[i][1]dp[i][1]状态2前iii个字符串出现了c和nc在n之前出现记为dp[i][2]dp[i][2]dp[i][2]。可以得出状态转移方程i1时dp[i][0]25,dp[i][1]1,dp[i][2]0;i1时dp[i][0]25,dp[i][1]1,dp[i][2]0;i1时dp[i][0]25,dp[i][1]1,dp[i][2]0;i1时dp[i][0]dp[i−1][0]∗25,i1时dp[i][0]dp[i-1][0]*25,i1时dp[i][0]dp[i−1][0]∗25,dp[i][1]dp[i−1][0]dp[i−1][1]∗25,dp[i][1]dp[i-1][0]dp[i-1][1]*25,dp[i][1]dp[i−1][0]dp[i−1][1]∗25,dp[i][2]dp[i−1][1]dp[i−1][2]∗26.dp[i][2]dp[i-1][1]dp[i-1][2]*26.dp[i][2]dp[i−1][1]dp[i−1][2]∗26.每次答案累加dp[i][2]。注意细节每次dp数组的值和答案要对1e97取模。我一开始想的时候考虑到幂运算看只有c和n组成的字符串有多少剩下的就是没有c和n的这个思路不对而且用了左移位运算做是不对的因为n100时会溢出。AC代码#includebits/stdc.husingnamespacestd;#defineintlonglongconstintmaxn1e65,mod1e97;intdp[maxn][3],n,ans;signedmain(){cinn;dp[1][0]25,dp[1][1]1,dp[1][2]0;for(inti2;in;i){dp[i][0]dp[i-1][0]*25%mod;dp[i][1](dp[i-1][0]dp[i-1][1]*25)%mod;dp[i][2](dp[i-1][1]dp[i-1][2]*26)%mod;ans(ansdp[i][2])%mod;}coutans;return0;}
