南宁网站建设专家,求一个全部用div做的网站,昆明市建设厅官方网站,建设官方网站的主要作用正题
题目链接:https://www.luogu.com.cn/problem/P4199 题目大意
给出一个只包含a,ba,ba,b的字符串
求有多少个不连续的回文子序列#xff08;字母回文#xff0c;位置对称#xff09; 1≤n≤1051\leq n\leq 10^51≤n≤105 解题思路
这个不连续一看就很nt#xff0c;考…正题
题目链接:https://www.luogu.com.cn/problem/P4199 题目大意
给出一个只包含a,ba,ba,b的字符串
求有多少个不连续的回文子序列字母回文位置对称
1≤n≤1051\leq n\leq 10^51≤n≤105 解题思路
这个不连续一看就很nt考虑求出所有的再减去连续的
对于每个对称轴来说a,ba,ba,b分开考虑贡献再乘起来再减去一两个都为空。
加入计算aaa的贡献就是看有多少对aaa以它为对称轴设为kkk对那么方案就是2k2^k2k。
怎么对于每个对称轴快速计算有多少对也就是每对aaa都会对他们的对称轴产生贡献假设iii于jjj都是aaa那么对称轴就是ij2\frac{ij}{2}2ij这个直接FFTFFTFFT就可以了
然后bbb同理。
然后字符串hash二分计算连续的方案就好了
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
#define ull unsigned long long
using namespace std;
const ll N4e510,P998244353,p1e97;
const ull g131;
ll n,l,a[N],b[N],r[N],ans;
ull pw[N],h[N],d[N];
char s[N];
ll power(ll x,ll b,ll P){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
void NTT(ll *f,ll op){for(ll i0;in;i)if(ir[i])swap(f[i],f[r[i]]);for(ll p2;pn;p1){ll tmppower(3,(P-1)/p,P),len(p1);if(op-1)tmppower(tmp,P-2,P);for(ll k0;kn;kp){ll buf1;for(ll ik;iklen;i){ll ttbuf*f[ilen]%P;f[ilen](f[i]-ttP)%P;f[i](f[i]tt)%P;bufbuf*tmp%P;}}}if(op-1){ll invnpower(n,P-2,P);for(ll i0;in;i)f[i]f[i]*invn%P;}return;
}
ull geth(ll l,ll r)
{return h[r]-h[l-1]*pw[r-l1];}
ull getd(ll l,ll r)
{return d[l]-d[r1]*pw[r-l1];}
signed main()
{scanf(%s,s);lstrlen(s);for(ll i0;il;i)a[i](s[i]a),b[i](s[i]b);n1;while(n2*l)n1;for(ll i0;in;i)r[i](r[i1]1)|((i1)?(n1):0);NTT(a,1);NTT(b,1);for(ll i0;in;i)a[i]a[i]*a[i]%P,b[i]b[i]*b[i]%P;NTT(a,-1);NTT(b,-1);for(ll i0;in;i)a[i](a[i]1)/2,b[i](b[i]1)/2;for(ll i0;in;i)(anspower(2,a[i]b[i],p)%p-1)%p;pw[0]1;for(ll i1;il;i)pw[i]pw[i-1]*g;for(ll i1;il;i)h[i]h[i-1]*gs[i-1]-a;for(ll il;i1;i--)d[i]d[i1]*gs[i-1]-a;for(ll i1;il;i){ll L1,Rmin(i,l-i1)-1;while(LR){ll mid(LR)1;if(geth(i-mid,imid)getd(i-mid,imid))Lmid1;else Rmid-1;}ans-R1;}for(ll i1;il;i){ll L1,Rmin(i,l-i);while(LR){ll mid(LR)1;if(geth(i-mid1,imid)getd(i-mid1,imid))Lmid1;else Rmid-1;}ans-R;}printf(%lld\n,(ans%pp)%p);return 0;
}
