fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. const int mod = 1000000007;
  7.  
  8.  
  9. vector<vector<long long>> mat_mul(vector<vector<long long>>& arr, vector<vector<long long>>& brr){
  10.  
  11. 	vector<vector<long long>> result(arr.size(), vector<long long>(brr[0].size()));
  12.  
  13. 	for(int i = 0; i < arr.size(); i++){
  14. 		for(int j = 0; j < brr[0].size(); j++){
  15. 			for(int k = 0; k < arr[0].size(); k++){
  16. 				result[i][j] += arr[i][k] * brr[k][j];
  17. 				result[i][j] %= mod;
  18. 			}
  19. 		}
  20. 	}
  21.  
  22. 	return result;
  23.  
  24. }
  25.  
  26. vector<vector<long long>> pow(vector<vector<long long>>& a, long long n){
  27. 	if(n == 1){
  28. 		return a;
  29. 	}
  30. 	auto result = pow(a, n / 2);
  31. 	result = mat_mul(result, result);
  32. 	if(n % 2 == 1){
  33. 		result = mat_mul(result, a);
  34. 	}
  35. 	return result;
  36. }
  37.  
  38. int main() {
  39.  
  40. 	ios_base::sync_with_stdio(0);
  41. 	cin.tie(0);
  42.  
  43. 	int t;
  44. 	cin >> t;
  45.  
  46. 	while(t--){
  47. 		long long n;
  48. 		cin >> n;
  49. 		if(n <= 2){
  50. 			string str;
  51. 			cin >> str;
  52. 			int answer = 0;
  53. 			int x = n == 1 ? 10 : 100;
  54. 			for(int i = 0; i < x; i++){
  55. 				bool check = true;
  56. 				for(int j = 1; j <= 6; j++){
  57. 					check &= (str[j - 1] == '0' and i % j != 0) or (str[j - 1] == '1' and i % j == 0) or (str[j - 1] == '2');
  58. 				}
  59. 				answer += check;
  60. 			}
  61. 			cout << answer << "\n";
  62. 		}else{
  63.  
  64. 			vector<bool> check(60, true);
  65.  
  66. 			string str;
  67. 			cin >> str;
  68.  
  69. 			for(int i = 1; i <= 6; i++){
  70. 				if(str[i - 1] == '0'){
  71. 					for(int j = 0; j < 60; j++){
  72. 						if(j % i == 0){
  73. 							check[j] = false;
  74. 						}
  75. 					}
  76. 				}else if(str[i - 1] == '1'){
  77. 					for(int j = 0; j < 60; j++){
  78. 						if(j % i != 0){
  79. 							check[j] = false;
  80. 						}
  81. 					}
  82. 				}
  83. 			}
  84.  
  85. 			int x1 = 0;
  86. 			int x2 = 0;
  87.  
  88. 			for(int i = 0; i < 60; i++){
  89. 				x1 += check[i];
  90. 			}
  91.  
  92. 			for(int i = 0; i < 40; i++){
  93. 				x2 += check[i];
  94. 			}
  95.  
  96. 			vector<vector<long long>> mat = {{10, 6}, {0, 1}};
  97. 			auto temp = pow(mat, n - 2);
  98. 			cout << ((temp[0][0] + temp[0][1]) % mod * x1 % mod + x2) % mod << "\n";
  99.  
  100. 		}
  101. 	}
  102.  
  103. 	return 0;
  104. }
Success #stdin #stdout 0.01s 5460KB
comments (?)
stdin
copy 
4
2 222201
1 111001
1 111111
4 222222
stdout
copy 
13
1
1
10000
https://ideone.com/m2Ku1k
language:
C++ (gcc 8.3)
created:
1 year 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!