fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fori(i, a, b) for (int i = a; i < b; ++i)
  4. #define ll long long
  5. #define m 4
  6. #define L(a) a.size()
  7.  
  8. const int MD = 15111992;
  9. const int ardv[m][m] = {{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}};
  10. const int arta[m][m] = {{0, 1, 0, 0}, {1, 1, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}};
  11. const int artb[m][m] = {{0, 1, 0, 0}, {1, 1, 0, 1}, {0, 0, 1, 0}, {0, 0, 0, 1}};
  12.  
  13. int n;
  14. string s1, s2, t, s;
  15.  
  16. struct matrix {
  17. 	int a[m][m];
  18. 	matrix() {
  19. 		fori(i, 0, m) fori(j, 0, m) a[i][j] = 0; 
  20. 	}
  21. 	matrix operator * (matrix b) {
  22. 		matrix c;
  23. 		fori(i, 0, m) fori(j, 0, m) c.a[i][j] = 0;
  24. 		fori(i, 0, m) fori(j, 0, m) fori(t, 0, m) 
  25. 			c.a[i][j] = (c.a[i][j] + (ll)a[i][t] * b.a[t][j] % MD) % MD;
  26. 		return c;
  27. 	}
  28. } ans, dv, ta, tb;
  29.  
  30. matrix multiPower(matrix a, int n) {
  31. 	if (!n) return dv;
  32. 	matrix g = multiPower(a, n / 2);
  33. 	g = g * g;
  34. 	return (n % 2) ? a * g : g;
  35. }
  36.  
  37. int compare(string a, string b, int j) {
  38. 	fori(i, 0, L(a)) 
  39. 		if (a[i] != b[j++]) return 0;
  40. 	return 1; 
  41. }
  42.  
  43. int get(string a, string b) {
  44. 	int tmp = 0;
  45. 	fori(i, 0, L(b) - L(a) + 1) tmp += compare(a, b, i); 
  46. 	return tmp;
  47. }
  48.  
  49. void enter() {
  50. 	cin >> n >> s1 >> s2 >> s;
  51. 	n -= 2;
  52. 	while (n && (L(s1) < L(s) || L(s2) < L(s))) {
  53. 		--n;
  54. 		t = s2 + s1; s1 = s2; s2 = t;
  55. 	}	
  56. }
  57.  
  58. void built() {
  59. 	fori(i, 0, m) fori(j, 0, m) {
  60. 		dv.a[i][j] = ardv[i][j];
  61. 		ta.a[i][j] = arta[i][j];
  62. 		tb.a[i][j] = artb[i][j];
  63. 	}
  64. 	ans.a[0][0] = get(s, s2);
  65. 	--n;
  66. 	ans.a[1][0] = get(s, s2 + s1); 
  67. 	ans.a[2][0] = get(s, s1 + s2) - get(s, s1) - get(s, s2);
  68. 	ans.a[3][0] = get(s, s2 + s2) - 2 * get(s, s2); 
  69. }
  70.  
  71. void solve() { 
  72. 	if (n % 2 == 0) ans = multiPower(tb * ta, n / 2) * ans; else {
  73. 		ans = ta * ans;
  74. 		ans = multiPower(ta * tb, n / 2) * ans;
  75. 	}
  76. 	cout << ans.a[1][0];
  77. }
  78.  
  79. int main() {
  80. 	enter();
  81. 	if (!n) { cout << get(s, s2); return 0; }
  82. 	built();
  83. 	solve();
  84. 	return 0;
  85. }
Success #stdin #stdout 0s 4284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/BrAsB7
language:
C++14 (gcc 8.3)
created:
5 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!