fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #define MOD 1000000
  4. typedef long long ll;
  5. using namespace std;
  6.  
  7. vector<vector<ll>> multiply(vector<vector<ll>> v1) {
  8. 	ll x00 = v1[0][0];
  9. 	ll x01 = v1[0][1];
  10. 	ll x10 = v1[1][0];
  11. 	ll x11 = v1[1][1];
  12. 	ll res00, res01, res10, res11;
  13. 	res00 = ((x00 * x00) % MOD + (x10 * x01) % MOD) % MOD;
  14. 	res01 = ((x00 * x01) % MOD + (x01 * x11) % MOD) % MOD;
  15. 	res10 = ((x10 * x00) % MOD + (x10 * x11) % MOD) % MOD;
  16. 	res11 = ((x10 * x01) % MOD + (x11 * x11) % MOD) % MOD;
  17. 	return{ {(res00 + MOD) % MOD, (res01 - MOD) % MOD}, {(res10 + MOD) % MOD, (res11 - MOD) % MOD} };
  18. }
  19. vector<vector<ll>> pow_mod(vector<vector<ll>> v, int p) {
  20.  
  21. 	if (p == 1) return v;
  22. 	if ((p % 2) == 0) {
  23. 		vector<vector<ll>> vct = (pow_mod(v, p / 2));
  24. 		return multiply(vct);
  25. 	}
  26. }
  27.  
  28. int main() {
  29. 	int k, n;
  30. 	cin >> k;
  31. 	for (int i = 0; i < k; i++)
  32. 	{
  33. 		cin >> n;
  34. 		if (n % 3)
  35. 		{
  36. 			cout << 0 << endl;
  37. 		}
  38. 		else
  39. 		{
  40. 			n /= 3;
  41. 			int p = 2;
  42. 			ll a1 = 1, a2 = 1;
  43. 			while (n > 0)
  44. 			{
  45. 				if (n & 1)
  46. 				{
  47. 					vector<vector<ll>> a = { {4,-1},{1,0} };
  48. 					a = pow_mod(a, p / 2);
  49. 					ll tmp1 = a1;
  50. 					ll tmp2 = a2;
  51. 					a1 = (tmp1 * a[0][0]) % MOD + (tmp2 * ((a[0][1] + MOD) % MOD)) % MOD;
  52. 					a2 = (tmp1 * a[1][0]) % MOD + (tmp2 * ((a[1][1] + MOD) % MOD)) % MOD;
  53. 				}
  54. 				p *= 2;
  55. 				n >>= 1;
  56. 			}
  57. 			cout << a1 % MOD << endl;
  58. 		}
  59. 	}
  60. 	return 0;
  61. }
Success #stdin #stdout 0s 4196KB
comments (?)
stdin
copy 
3
3
4
6
stdout
copy 
3
0
11
https://ideone.com/yaKHhx
Задача№236. Триомино
language:
C++ (gcc 8.3)
created:
4 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!