fork download
copy 
  1. #include <cstdlib>
  2. #include <cctype>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <vector>
  8. #include <string>
  9. #include <iostream>
  10. #include <sstream>
  11. #include <map>
  12. #include <unordered_map>
  13. #include <set>
  14. #include <unordered_set>
  15. #include <queue>
  16. #include <stack>
  17. #include <fstream>
  18. #include <numeric>
  19. #include <iomanip>
  20.  
  21. using namespace std;
  22.  
  23. typedef long long ll;
  24. typedef pair<int,int> PP;
  25.  
  26. class CyclesNumber {
  27. 	public:
  28. 	ll G[310][310];
  29. 	ll MOD = 1E9 + 7;
  30.  
  31. 	ll power(ll a, ll b) {
  32. 		ll res = 1;
  33. 		ll crt = a;
  34. 		while (b > 0) {
  35. 			if (b % 2 == 1) {
  36. 				res *= crt;
  37. 				res %= MOD;
  38. 			}
  39. 			b /= 2;
  40. 			crt *= crt;
  41. 			crt %= MOD;
  42. 		}
  43. 		return res;
  44. 	}
  45.  
  46. 	ll F[100010];
  47. 	ll I[100010];
  48.  
  49. 	ll nchoosek(int a, int b) {
  50. 		if (b == 0 || a == b) return 1;
  51. 		ll res = F[a] * I[b];
  52. 		res %= MOD;
  53. 		res *= I[a - b];
  54. 		res %= MOD;
  55. 		return res;
  56. 	}
  57.  
  58. 	void init() {
  59. 		memset(G, 0, sizeof(G));
  60. 		memset(F, 0, sizeof(F));
  61. 		memset(I, 0, sizeof(I));
  62. 		F[0] = 1;
  63. 		I[0] = 1;
  64. 		for (ll i = 1;i <= 1E5;i++) {
  65. 			F[i] = F[i - 1] * i;
  66. 			F[i] %= MOD;
  67. 			I[i] = power(F[i], MOD - 2);
  68. 		}
  69. 		G[1][1] = 1;
  70. 		for (int i = 2;i <= 300;i++) {
  71. 			for (int j = 1;j <= i;j++) {
  72. 				ll res = power(j, i);
  73. 				for (int k = 1;k < j;k++) {
  74. 					res += MOD - ((nchoosek(j, k) * G[k][i]) % MOD);
  75. 					res %= MOD;
  76. 				}
  77. 				G[j][i] = res;
  78. 			}
  79. 		}
  80. 		return;
  81. 	}
  82.  
  83. 	vector <int> getExpectation(vector <int> n, vector <int> m)  {
  84. 		unordered_set<int> X;
  85. 		unordered_map<int, ll> Y[310];
  86. 		for (int i = 0;i < n.size();i++) X.insert(n[i]);
  87. 		init();
  88. 	    ll A[100010];
  89. 	    ll B[100010];
  90. 	    memset(A, 0, sizeof(A));
  91. 	    memset(B, 0, sizeof(B));
  92. 	    A[0] = 1;
  93. 	    for (ll i = 1;i <= 300;i++) {
  94. 	    	ll sum = 0;
  95. 	    	for (ll j = 1;j <= 1E5;j++) {
  96. 	    		B[j] = (j - 1) * B[j - 1];
  97. 	    		B[j] %= MOD;
  98. 	    		B[j] += A[j - 1];
  99. 	    		B[j] %= MOD;
  100. 	    		sum += B[j] * I[j];
  101. 	    		sum %= MOD;
  102. 	    		if (X.find(j) != X.end()) Y[i][j] = sum;
  103. 	    	}
  104. 	    	swap(A, B);
  105. 	    	memset(B, 0, sizeof(B));
  106. 	    }
  107. 	    vector<int> ans;
  108. 	    for (int i = 0;i < n.size();i++) {
  109. 	    	ll N = n[i];
  110. 	    	ll M = m[i];
  111. 	    	ll res = 0;
  112. 	    	for (int a = 1;a <= M;a++) {
  113. 	    		res += Y[a][N] * G[a][M];
  114. 	    		res %= MOD;
  115. 	    	}
  116. 	    	res *= F[N];
  117. 	    	res %= MOD;
  118. 	    	if (M == 0) res = F[N];
  119. 	    	ans.push_back(res);
  120. 	    }
  121. 	    return ans;
  122. 	}
  123. };
Compilation error #stdin compilation error #stdout 5s 7236KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/lib/gcc/i586-linux-gnu/5/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/cqBGdF
language:
C++14 (gcc 8.3)
created:
8 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!