企业网站建设包含哪些内容,专业高端网站建设,市场营销策划方案模板,外贸服饰网站建设\(\\\) \(Description\) 一个由小写字母构成的长为\(N\)的字符串#xff0c;求前\(K\)长的奇数长度回文子串长度之积#xff0c;对\(19930726\)取模后的答案。 \(N\in [1,10^6]\)#xff0c;\(K\in [1,10^{12}]\)\(\\\) \(Solution\) \(Manacher\)处理出所有位置的回文半径求前\(K\)长的奇数长度回文子串长度之积对\(19930726\)取模后的答案。 \(N\in [1,10^6]\)\(K\in [1,10^{12}]\)\(\\\) \(Solution\) \(Manacher\)处理出所有位置的回文半径因为答案要求奇数长度所以不用插入特殊字符在原串上直接跑\(Manacher\)就好回文半径内的以当前点为回文中心的每一个子串都是回文串。所以开一个长度的桶只给回文半径对应的最长子串长度打标记显然一个标记代表着后面所有位置都\(1\)所以计算的时候一个长度的回文子串个数是长度标记的前缀和。要求的\(K\)非常大快速幂处理。\(\\\) \(Code\) #includecmath
#includecstdio
#includecctype
#includecstdlib
#includecstring
#includeiostream
#includealgorithm
#define N 1000010
#define R register
#define gc getchar
#define mod 19930726
using namespace std;
typedef long long ll;char c,s[N];ll m,res1,sum;int n,len[N],cnt[N];inline void init(){scanf(%d%lld,n,m);while(!isalpha(cgc()));s[1]c; s[0][; s[n1]];for(R int i2;in;i) s[i]gc();
}inline void manacher(){for(R int i1,p0,mr0;in;i){len[i]imr?1:min(mr-i1,len[(p1)-i]);while(s[i-len[i]]s[ilen[i]]) len[i];if(ilen[i]-1mr){pi;mrilen[i]-1;}cnt[(len[i]1)-1];}
}inline ll qpow(ll x,ll t){ll res1;while(t){if(t1) (res*x)%mod;(x*x)%mod; t1;}return res;
}int main(){init();manacher();for(R int i((n/2)1)1;i1;i-2){sum(ll)cnt[i];if(summ){printf(%lld,(res*qpow(i,m))%mod);return 0;}(res*qpow(i,sum))%mod; m-sum;}puts(-1);return 0;
} 转载于:https://www.cnblogs.com/SGCollin/p/9690070.html
