fork download
copy 
  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <fstream>
  6. #include <iostream>
  7. #include <cstdlib>
  8.  
  9. #define rep(i, l, r) for(int i = l; i <= r; i++)
  10. #define down(i, l, r) for(int i = l; i >= r; i--)
  11. #define MS 56789
  12. #define MAX 1037671823
  13.  
  14. using namespace std;
  15.  
  16. int n, m, a, q, v[67][23][23], h[23];
  17. char s[23];
  18. bool b[10];
  19.  
  20. void Calculate(int x, int o)
  21. {
  22. 	if (x == 1) 
  23. 		rep(i, 0, m-1) rep(j, 0, m-1) v[o][i][j] = v[0][i][j];
  24. 	else if (x % 2 == 1)
  25. 	{
  26. 		Calculate(x-1, o+1);
  27. 		rep(i, 0, m-1) rep(j, 0, m-1) rep(k, 0, m-1) v[o][i][j] = (v[o][i][j] + v[o+1][i][k] * v[0][k][j]) % q;
  28. 	}
  29. 	else
  30. 	{
  31. 		Calculate(x / 2, o+1);
  32. 		rep(i, 0, m-1) rep(j, 0, m-1) rep(k, 0, m-1) v[o][i][j] = (v[o][i][j] + v[o+1][i][k] * v[o+1][k][j]) % q;
  33. 	}
  34. }
  35.  
  36. int main()
  37. {
  38. 	scanf("%d%d%d%s", &n, &m, &q, s);
  39. 	h[0] = -1; 
  40. 	rep(i, 1, m-1) 
  41. 	{
  42. 		a = h[i-1];
  43. 		while (a != -1 && s[a+1] != s[i]) a = h[a];
  44. 		if (s[a+1] == s[i]) h[i] = a+1; else h[i] = -1;
  45. 	}
  46. 	rep(i, 0, m-1)
  47. 	{
  48. 		rep(j, 0, 9) b[j] = true; v[0][i][0] = 10;
  49. 		a = i-1;
  50. 		while (true)
  51. 		{
  52. 			if (b[s[a+1]-'0']) b[s[a+1]-'0'] = false, v[0][i][0]--, v[0][i][a+2]++;
  53. 			if (a == -1) break; else a = h[a];
  54. 		}
  55. 	}
  56. 	Calculate(n, 1);
  57. 	a = 0; rep(i, 0, m-1) a += v[1][0][i]; a %= q; printf("%d\n", a);
  58. 	return 0;
  59. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
4 3 100 
111
stdout
copy 
81
https://ideone.com/HuJrHO
BZOJ 1009
language:
C++ (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!