fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace::std;
  3.  
  4. const int MOD = 1000000000 + 7;
  5. const int N = 100000+5;
  6. const int E = 26;
  7.  
  8. int n;
  9. int k;
  10. bool valid[E];
  11. int memo[N][E];
  12.  
  13. int main(){
  14. 	scanf("%d %d",&n,&k);
  15. 	char c;
  16. 	for(int i=0; i<k; i++){
  17. 		c = getchar();
  18. 		while(!isalpha(c)) c = getchar();
  19. 		valid[c - 'a'] = true;
  20. 	}
  21. 	int prevSum = 0;
  22. 	for(int i=0; i<E; i++){
  23. 		if(valid[i]){
  24. 			memo[1][i] = 1;
  25. 			prevSum += 1;
  26. 		}
  27. 	}
  28. 	for(int i=2; i<=n; i++){
  29. 		for(int j=0; j<E; j++){
  30. 			if(i&1){
  31. 				if(valid[j]) memo[i][j] = prevSum - memo[i-1][j];
  32. 			}
  33. 			else{
  34. 				memo[i][j] = prevSum - memo[i-1][j];
  35. 			}
  36. 		}
  37. 		prevSum = 0;
  38. 		for(int j=0; j<E; j++){
  39. 			prevSum += memo[i][j];
  40. 			if(prevSum >= MOD) prevSum -= MOD;
  41. 		}
  42. 	}
  43. 	int ans = 0;
  44. 	for(int i=0; i<E; i++){
  45. 		ans += memo[n][i];
  46. 		if(ans >= MOD) ans -= MOD;
  47. 	}
  48. 	cout << ans << endl;
  49. 	return 0;
  50. }
Success #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
2 1
a
stdout
copy 
25
https://ideone.com/RSZ3nW
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!