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.  
  53. 		}else{
  54.  
  55. 			vector<bool> check(60, true);
  56.  
  57. 			string str;
  58. 			cin >> str;
  59.  
  60. 			int x1 = 60;
  61. 			int x2 = 60;
  62.  
  63. 			for(int i = 1; i <= 6; i++){
  64. 				if(str[i] == '0'){
  65. 					for(int j = 0; j < 60; j++){
  66. 						x1 -= (j % i == 0) && check[j];
  67. 						if(j < 40){
  68. 							x2 -= (j % i == 0) && check[j];
  69. 						}
  70. 						check[j] = check[j] && (j % i == 0);
  71. 					}
  72. 				}else if(str[i] == '1'){
  73. 					for(int j = 0; j < 60; j++){
  74. 						x1 -= (j % i != 0) && check[j];
  75. 						if(j < 40){
  76. 							x2 -= (j % i != 0) && check[j];
  77. 						}
  78. 						check[j] = check[j] && (j % i != 0);
  79. 					}
  80. 				}
  81. 			}
  82.  
  83. 			vector<vector<long long>> mat = {{10, 6}, {0, 1}};
  84. 			pow(mat, n - 2);
  85. 			cout << ((mat[0][0] + mat[0][1]) % mod * x1 % mod + x2) % mod << "\n";
  86.  
  87. 		}
  88. 	}
  89.  
  90. 	return 0;
  91. }
Success #stdin #stdout 0.01s 5520KB
comments (?)
stdin
copy 
4
2 222201
1 111001
1 111111
2 222222
stdout
copy 
Standard output is empty
https://ideone.com/eB4Adl
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!