fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
  4. #define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
  5. #define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
  6. #define rep(i, c)  for(auto &(i) : (c))
  7. #define x     first
  8. #define y     second
  9. #define pb  push_back
  10. #define PB  pop_back()
  11. #define iOS  ios_base::sync_with_stdio(false)
  12. #define sqr(a)  (((a) * (a)))
  13. #define all(a)  a.begin() , a.end()
  14. #define error(x) cerr << #x << " = " << (x) <<endl
  15. #define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
  16. #define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
  17. #define coud(a,b) cout<<fixed << setprecision((b)) << (a)
  18. #define L(x)  ((x)<<1)
  19. #define R(x)  (((x)<<1)+1)
  20. #define umap  unordered_map
  21. //#define max(x,y)  ((x) > (y) ? (x) : (y))
  22. #define double long double
  23. typedef long long ll;
  24. typedef pair<int,int>pii;
  25. typedef vector<int> vi;
  26. typedef complex<double> point;
  27. inline vi prefix(string p){
  28. 	vi pi;
  29. 	int m = p.size();
  30. 	For(i,0,m)
  31. 		pi.pb(-1);
  32. 	int k = -1;
  33. 	For(i,1,m){
  34. 		while(k != -1 && p[k+1] != p[i])
  35. 			k = pi[k];
  36. 		if(p[k+1] == p[i])
  37. 			k++;
  38. 		pi[i] = k;
  39. 	}
  40. 	return pi;
  41. }
  42. set<int> s;
  43. inline void shift(string p){
  44. 	vector<int> pi = prefix(p);
  45. 	int m = p.size();
  46. 	int k = pi[m-1];
  47. 	while(k!=-1){
  48. 		s.insert(m-k);
  49. 		k = pi[k];
  50. 	}
  51. }
  52. int main(){
  53.     iOS;
  54. 	ll n,m;
  55. 	cin >> n >> m;
  56. 	string p;
  57. 	cin >> p;
  58. 	vi pi = prefix(p);
  59. 	shift(p);
  60. 	vi v;
  61. 	For(i,0,m){
  62. 		int a;
  63. 		cin >> a;
  64. 		v.pb(a);
  65. 	}
  66. 	bool ok = true;
  67. 	For(i,1,v.size()){
  68. 		ll r = v[i] , l=v[i-1];
  69. 		if(r<(l+p.size()) && s.find((r-l+1))==s.end()){
  70. 				cout << 0 << endl;
  71. 				ok = false;
  72. 				break;
  73. 		}
  74. 		if((p.size()+r-1)>n && ok){
  75. 				cout<< 0 <<endl;
  76. 				ok = false;
  77. 				break;
  78. 		}
  79. 	}
  80. 	ll x = n;
  81. 	if(ok){
  82. 		v.pb(2000000000);
  83. 		For(i,0,v.size()-1)
  84. 			x -= min((int)p.size(),v[i+1]-v[i]);
  85.  
  86. 	}
  87. 	ll ans=1;
  88. 	if(x < 0 && ok){
  89. 				cout<< 0 <<endl;
  90. 				ok = false;
  91. 	}
  92. 	For(i,0,x)
  93. 		ans = (ans*(ll)26) % 1000000007;
  94. 	if(ok)
  95. 		cout<< ans <<endl;
  96. }
  97.  
  98.  
  99.  
Runtime error #stdin #stdout 0s 3280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hdKn12
language:
C++14 (gcc 8.3)
created:
9 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!