| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 21999 |
2017-04-28T17:02:04 Z |
gs14004 |
흑백 (kriii4_G) |
C++11 |
|
366 ms |
33284 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
lint ipow(lint x, lint p){
lint ret = 1, piv = x % mod;
while(p){
if(p&1) ret *= piv;
piv *= piv;
ret %= mod;
piv %= mod;
p >>= 1;
}
return ret % mod;
}
lint pwr[2000005], ipw[2000005];
lint fact[1005], invf[1005];
int n, m;
lint ncr(int x, int y){
if(y < 0 || x < y) return 0;
return fact[x] * (invf[y] * invf[x-y] % mod) % mod;
}
lint solve(int n, int m){
lint ans = 0;
for(int i=1; i<=n; i++){
for(int k=1; k+i<=n; k++){
ans += (ncr(n, i) * ncr(n-i, k) % mod) *
((ipow(ipw[i] + 1, m) - 1) * (ipow(ipw[k] + 1, m) - 1) % mod) % mod;
}
}
return ans;
}
lint solve2(){
lint ans = 0;
for(int i=1; i<=n; i++){
for(int j=1; j+i<=n; j++){
lint aux = ipow(ipw[j] + 1, m) * (ipow((ipw[i] * ipow(ipw[j] + 1, mod - 2) + 1) % mod, m) + mod - 1) % mod;
aux -= ipow(ipw[i] + 1, m) - 1;
aux += mod;
aux %= mod;
ans += (ncr(n, i) * ncr(n-i, j) % mod) * aux;
ans %= mod;
}
}
return ans;
}
int main(){
cin >> n >> m;
pwr[0] = ipw[0] = 1;
for(int i=1; i<=n*m*2; i++){
pwr[i] = pwr[i-1] * 2 % mod;
ipw[i] = ipw[i-1] * ((mod + 1) / 2) % mod;
}
fact[0] = invf[0] = 1;
for(int i=1; i<=max(n, m); i++){
fact[i] = fact[i-1] * i % mod;
invf[i] = ipow(fact[i], mod-2);
}
lint x = solve(n, m) + solve(m, n) - solve2() + mod;
cout << x % mod;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
33284 KB |
Output is correct |
| 2 |
Correct |
0 ms |
33284 KB |
Output is correct |
| 3 |
Correct |
0 ms |
33284 KB |
Output is correct |
| 4 |
Correct |
0 ms |
33284 KB |
Output is correct |
| 5 |
Correct |
0 ms |
33284 KB |
Output is correct |
| 6 |
Correct |
0 ms |
33284 KB |
Output is correct |
| 7 |
Correct |
0 ms |
33284 KB |
Output is correct |
| 8 |
Correct |
0 ms |
33284 KB |
Output is correct |
| 9 |
Correct |
0 ms |
33284 KB |
Output is correct |
| 10 |
Correct |
0 ms |
33284 KB |
Output is correct |
| 11 |
Correct |
0 ms |
33284 KB |
Output is correct |
| 12 |
Correct |
0 ms |
33284 KB |
Output is correct |
| 13 |
Correct |
0 ms |
33284 KB |
Output is correct |
| 14 |
Correct |
0 ms |
33284 KB |
Output is correct |
| 15 |
Correct |
0 ms |
33284 KB |
Output is correct |
| 16 |
Correct |
0 ms |
33284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
33284 KB |
Output is correct |
| 2 |
Correct |
69 ms |
33284 KB |
Output is correct |
| 3 |
Correct |
276 ms |
33284 KB |
Output is correct |
| 4 |
Correct |
156 ms |
33284 KB |
Output is correct |
| 5 |
Correct |
106 ms |
33284 KB |
Output is correct |
| 6 |
Correct |
86 ms |
33284 KB |
Output is correct |
| 7 |
Correct |
183 ms |
33284 KB |
Output is correct |
| 8 |
Correct |
6 ms |
33284 KB |
Output is correct |
| 9 |
Correct |
33 ms |
33284 KB |
Output is correct |
| 10 |
Correct |
216 ms |
33284 KB |
Output is correct |
| 11 |
Correct |
233 ms |
33284 KB |
Output is correct |
| 12 |
Correct |
166 ms |
33284 KB |
Output is correct |
| 13 |
Correct |
56 ms |
33284 KB |
Output is correct |
| 14 |
Correct |
293 ms |
33284 KB |
Output is correct |
| 15 |
Correct |
113 ms |
33284 KB |
Output is correct |
| 16 |
Correct |
126 ms |
33284 KB |
Output is correct |
| 17 |
Correct |
113 ms |
33284 KB |
Output is correct |
| 18 |
Correct |
126 ms |
33284 KB |
Output is correct |
| 19 |
Correct |
96 ms |
33284 KB |
Output is correct |
| 20 |
Correct |
36 ms |
33284 KB |
Output is correct |
| 21 |
Correct |
359 ms |
33284 KB |
Output is correct |
| 22 |
Correct |
366 ms |
33284 KB |
Output is correct |
| 23 |
Correct |
366 ms |
33284 KB |
Output is correct |
| 24 |
Correct |
366 ms |
33284 KB |
Output is correct |
