fork(3) download
copy 
  1. #include <iostream>
  2. #include <cassert>
  3. #include <vector>
  4. #include <set>
  5. #include <cstdio>
  6. #include <algorithm>
  7. #include <cstring>
  8. using namespace std;
  9.  
  10. #define maxn 2222222
  11. #define base1 1000003LL
  12. #define base2 239LL
  13. #define mod1 1000000007LL
  14. #define mod2 1000000009LL
  15.  
  16. pair<long long,long long>a[maxn];
  17. int an,i,j,N,K,l,r,lT,k,f[maxn],P[maxn],was[maxn],cycles,Count[maxn],q,c[maxn],Q[maxn],size,R[maxn],s[maxn];
  18. long long pw1[maxn],pw2[maxn],sha1[maxn],sha2[maxn],pw,ret;
  19. char T[maxn];
  20.  
  21. pair<long long,long long>gethash(int j,int x){ // hash of a [j; j+x) substring
  22. 	return make_pair(((sha1[j]-sha1[j+x]+mod1)*pw1[j])%mod1,((sha2[j]-sha2[j+x]+mod2)*pw2[j])%mod2);
  23. }
  24.  
  25. void getOddSubpalindromes(){	// Manacher algo for finding all odd sub palindromes. one can prove that there will be no more than N distinct such palindromes
  26. 	for(i=0,l=0,r=-1;i<lT;i++){
  27. 		k=(i>r?0:min(f[l+r-i],r-i))+1;
  28. 		while(i+k<lT&&i-k>=0&&T[i+k]==T[i-k]){
  29. 			a[++an]=gethash(i-k,2*k+1);
  30. 			++k;
  31. 		}
  32. 		while(i+k>=lT||i-k<0||T[i+k]!=T[i-k])--k;
  33. 		f[i]=k;
  34. 		a[++an]=gethash(i-k,2*k+1);
  35. 		a[++an]=gethash(i,1);
  36. 		if(i+k>r)l=i-k,r=i+k;
  37. 	}
  38. }
  39.  
  40. void getEvenSubpalindromes(){ // Manacher algo for finding all even sub palindromes. one can prove that there will be no more than N distinct such palindromes
  41. 	for(i=0;i<lT;i++)f[i]=0;
  42. 	for(i=0,l=0,r=-1;i<lT;i++){
  43. 		k=(i>r?0:min(f[l+r-i+1],r-i+1))+1;
  44. 		while(i+k-1<lT&&i-k>=0&&T[i-k]==T[i+k-1]){
  45. 			a[++an]=gethash(i-k,2*k);
  46. 			++k;
  47. 		}
  48. 		f[i]=--k;
  49. 		if(i+k-1>r)l=i-k,r=i+k-1;
  50. 	}
  51. }
  52.  
  53. void buildHash(){ // preprocess hashes
  54. 	pw1[0]=pw2[0]=1;
  55. 	for(i=1;i<=lT;i++)pw1[i]=(pw1[i-1]*base1)%mod1,pw2[i]=(pw2[i-1]*base2)%mod2;
  56. 	sha1[lT-1]=sha2[lT-1]=T[lT-1];
  57. 	for(i=lT-2;i+1;i--){
  58. 		sha1[i]=(sha1[i+1]+pw1[lT-i-1]*T[i])%mod1,sha2[i]=(sha2[i+1]+pw2[lT-i-1]*T[i])%mod2;
  59. 	}
  60. }
  61.  
  62. long long carry=0;
  63. int bn,b[maxn];
  64.  
  65. void outputTheAnswer(){
  66. 	carry=0;
  67. 	for(i=maxn-1;i+1;i--){
  68. 		carry=carry*an+Count[i];
  69. 		if(carry>=size||bn){
  70. 			b[++bn]=carry/size;
  71. 			carry%=size;
  72. 		}
  73. 	}
  74. 	assert(carry==0);
  75. 	c[c[0]=1]=0;
  76. 	for(i=1;i<=bn;i++){
  77. 		for(j=1;j<=c[0];j++)c[j]*=an;
  78. 		c[0]+=20,c[1]+=b[i];
  79. 		for(j=1;j<=c[0];j++){
  80. 			c[j+1]+=c[j]/10;
  81. 			c[j]%=10;
  82. 		}
  83. 		while(c[0]>1&&c[c[0]]==0)--c[0];
  84. 	}
  85. 	for(i=c[0];i;i--)putchar('0'+c[i]);
  86. 	puts("");
  87. }
  88.  
  89. vector<int>vec;
  90. set<vector<int> >S;
  91.  
  92. void go(int*A){ // count the number of cycles in the permutation
  93. 	int i;
  94. 	vec.clear();
  95. 	for(i=1;i<=N;i++)vec.push_back(A[i]);
  96. 	if(S.find(vec)!=S.end())return; // uniqueeness checking (maybe, it's not necessary)
  97. 	S.insert(vec);
  98. 	++size;cycles=0;
  99. 	for(i=1;i<=N;i++)if(was[i]!=size){
  100. 		++cycles;
  101. 		for(q=i;was[q]!=size;q=A[q])was[q]=size;
  102. 	}
  103. 	++Count[cycles];
  104. }
  105.  
  106. int main (int argc, char * const argv[]) {
  107. 	gets(T);
  108. 	lT=strlen(T);
  109. 	buildHash();
  110. 	getOddSubpalindromes();
  111. 	getEvenSubpalindromes();
  112. 	sort(a+1,a+an+1);
  113. 	an=unique(a+1,a+an+1)-(a+1);
  114. 	if(an==1){ // if there's only one palindrome (<=> |T|=1)
  115. 		cout<<1<<endl;
  116. 		return 0;
  117. 	}
  118. 	scanf("%d",&N);
  119. 	for(i=1;i<=N;i++){ // generating all reachable permutations
  120. 		// cyclic shift:
  121. 		for(j=1;j<i;j++)P[j]=N-i+j+1; 
  122. 		for(j=i;j<=N;j++)P[j]=j-i+1;
  123. 		go(P);
  124. 		// reversed cyclic shift:
  125. 		reverse(P+1,P+N+1);
  126. 		go(P);
  127. 	}
  128. 	for(i=1;i+1<maxn;i++){ // managing bignums
  129. 		Count[i+1]+=Count[i]/an;
  130. 		Count[i]%=an;
  131. 	}
  132. 	outputTheAnswer();
  133.     return 0;
  134. }
  135.  
Success #stdin #stdout 0.08s 187968KB
comments (?)
stdin
copy 
aba
4
stdout
copy 
21
https://ideone.com/0VHJrP
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!