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

题意：

　　给定 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)];

　　别忘取模……

代码：

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #define ll long long

 using namespace std;

 const int N=;

 ll f[N],m,n,k,s,w;

 int main(){

     scanf("%lld%lld%lld",&n,&s,&m);

     f[]=;for(int i=;i<=n;i++)

     f[i]=(f[i-]*s-f[(i+)>>])%m;

     printf("%lld\n",f[n]%m);

     return ;

 }

巴特西

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

题意：

分析：

最新文章

热门文章