fork download
copy 
  1. using namespace std;
  2.  
  3. #include <iostream>
  4. #include <cstring>
  5. #include <vector>
  6. #include <fstream>
  7.  
  8. #define mod 1000000007
  9.  
  10. long long ans = 1;
  11.  
  12. struct matrix {
  13. 	long long a[20][20];
  14. 	matrix() {memset(a,0,sizeof(a));}
  15. 	matrix(int v[20][20]) {memcpy(a,v,sizeof(a));}
  16. 	void addE() {for(int i = 0;i < 20;i++) a[i][i]++;}
  17. 	matrix operator *(const matrix &b) {
  18. 		matrix ret;
  19. 		for(int i = 0;i < 20;i++)
  20. 			for(int j = 0;j < 20;j++)
  21. 				for(int k = 0;k < 20;k++)
  22. 					ret.a[i][k]=(ret.a[i][k] + a[i][j] * 1LL * b.a[j][k]) % mod;
  23. 		return ret;
  24. 	}
  25. };
  26.  
  27. matrix fastpow(matrix x,long long a) {
  28. 	matrix ret;ret.addE();
  29. 	while(a) {
  30. 		if(a & 1) ret = ret*x;
  31. 		x = x * x;
  32. 		a >>= 1;
  33. 	}
  34. 	return ret;
  35. }
  36.  
  37. int N,M,K;
  38.  
  39. long long arr[20];
  40.  
  41. vector<int> edges[100];
  42. bool dp[20];
  43.  
  44. void solve(int n) {
  45. 	if(n == 0) return;
  46. 	if(dp[n]) return;
  47. 	dp[n] = 1;
  48. 	bool isChild[20];
  49. 	memset(isChild,0,sizeof(isChild));
  50. 	for(int i = 0;i < edges[n].size();++i) {
  51. 		int next = edges[n][i];
  52. 		isChild[next] = true;
  53. 		solve(next);
  54. 	}
  55. 	matrix mval[20];
  56. 	mval[0].a[0][0] = isChild[0];
  57. 	for(int i = 1;i <= n;++i) {
  58. 		long long times = arr[i] / arr[i - 1];
  59. 		mval[i] = fastpow(mval[i - 1],times);
  60. 		for(int j = 0;j <= i;++j) {
  61. 			if(isChild[i]) {
  62. 				mval[i].a[i][j]++;
  63. 				if(mval[i].a[i][j] >= mod) mval[i].a[i][j] -= mod;
  64. 			}
  65. 		}
  66. 	}
  67. 	long long res = 0;
  68. 	for(int i = 0;i <= n;++i) {
  69. 		res += mval[n].a[i][0];
  70. 		if(res >= mod) res -= mod;
  71. 	}
  72. 	ans = (ans * res) % mod;
  73. 	return;
  74. }
  75.  
  76.  
  77. int main() {
  78.  
  79. 	cin >> N >> M;
  80. 	for(int i = 0;i < N;++i) {
  81. 		cin >> arr[i];
  82. 	}
  83.  
  84. 	for(int i = 0;i < M;++i) {
  85. 		int a,b;
  86. 		cin >> a >> b;
  87. 		a--;b--;
  88. 		if(arr[a] > arr[b]) {
  89. 			swap(a,b);
  90. 		}
  91. 		edges[b].push_back(a);
  92. 	}
  93. 	solve(N - 1);
  94. 	cout << ans << endl;
  95. }
Success #stdin #stdout 0s 4344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/KtRakA
language:
C++14 (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!