手机网站 优化,戒烟网页设计作品欣赏,网站建设平台选用,天津品牌网站建设公司正题
luogu链接:https://www.luogu.org/problemnew/show/CF7D 题目大意
定义kkk级回文串为一个字符串的(1,⌊n/2⌋)(1,\lfloor n/2 \rfloor)(1,⌊n/2⌋)和(n−⌊n/2⌋,n)(n-\lfloor n/2 \rfloor,n)(n−⌊n/2⌋,n)都是k−1k-1k−1级回文串。
求这个字符的所有前缀的回文串等级…正题
luogu链接:https://www.luogu.org/problemnew/show/CF7D 题目大意
定义kkk级回文串为一个字符串的(1,⌊n/2⌋)(1,\lfloor n/2 \rfloor)(1,⌊n/2⌋)和(n−⌊n/2⌋,n)(n-\lfloor n/2 \rfloor,n)(n−⌊n/2⌋,n)都是k−1k-1k−1级回文串。
求这个字符的所有前缀的回文串等级和。 解题思路
其实挺简单的如果一个前缀是回文串那么fif⌊i/2⌋1f_if_{\lfloor i/2\rfloor}1fif⌊i/2⌋1 然后答案就是∑i1nfi\sum_{i1}^nf_i∑i1nfi 然后字符串hashhashhash判断回文串就好了 codecodecode
#includecstdio
#includealgorithm
#includecstring
#define ull unsigned long long
using namespace std;
const int N5e610;
const ull p233;
int n,f[N],ans;
char s[N];
ull ha[N],pows[N],fha[N];
ull ask(int l,int r)
{return ha[r]-ha[l-1]*pows[r-l1];}
ull fask(int l,int r)
{return fha[l]-fha[r1]*pows[r-l1];}
int main()
{scanf(%s,s1);nstrlen(s1);pows[0]1;for(int i1;in;i){pows[i]pows[i-1]*p;ha[i]ha[i-1]*p(s[i]-a);}for(int in;i1;i--)fha[i]fha[i1]*p(s[i]-a);ansf[1]1;for(int i2;in;i)if(ask(1,i/2)fask((i1)/21,i))f[i]f[i/2]1,ansf[i];printf(%d,ans);
}
