【2019 1月集训 Day1】回文的后缀

时间:2021-04-11 09:49:19

题意:

  给定 n,s,求有多少个字符集大小为 s ,长度为 n 的字符串,使得其不存在一个长度大于 1 回文后缀

  答案对 m 取模。

分析:

  考场见到计数题的链式反应,想写暴力—>暴力难写—>不会暴力—>弃疗—>爆零。

  今天考试也不例外。但是逐渐思想过于摸化,没想到今天T2这么简单的一个递推,竟然不会写,我好弱啊,大概是学废了。

  对于这道题目,我们想到,后缀其实就是前缀(把字符串倒过来即可)我们设f[i]表示长度为i的满足题意的最长回文前缀是1的字符串有多少个,f[0]=1,在转移时,我们啥都不考虑,直接加一个字母。

  但是可能原串是这样的,最长回文前缀长度为1,我们加了一个字母之后,突然最长回文前缀长度就变成了i,比如“abbbbbb”最长回文前缀是1,但是,假如我们加入一个a,那么这个长度立刻就变成了8,我们就要把不和法的减去,所以考虑长度为p的回文串(不存在一个大于1的回文串是它的前缀)的数目,其实我们把把半个串确定了,整个回文串就确定了。

  所以方案数是f[ceil(i/2)],(ceil()函数代表向上取整)。

  最终的递推式子就是f[i]=f[i-1]*s-f[ceil(i/2)];

  别忘取模……

代码:

 

【2019 1月集训 Day1】回文的后缀【2019 1月集训 Day1】回文的后缀
 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<cmath>
 6 #define ll long long
 7 using namespace std;
 8 const int N=10000005;
 9 ll f[N],m,n,k,s,w;
10 int main(){
11     scanf("%lld%lld%lld",&n,&s,&m);
12     f[0]=1;for(int i=1;i<=n;i++)
13     f[i]=(f[i-1]*s-f[(i+1)>>1])%m;
14     printf("%lld\n",f[n]%m);
15     return 0;
16 }
dp