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