| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 786150 |
2023-07-18T04:57:08 Z |
박상훈(#10027) |
NoM (RMI21_nom) |
C++17 |
|
51 ms |
23000 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MOD = 1e9 + 7;
constexpr int INV2 = (MOD+1) / 2;
ll fact[4040], factINV[4040], dp[2020][2020];
ll pw(ll a, ll e){
if (!e) return 1;
ll ret = pw(a, e/2);
if (e&1) return ret * ret % MOD * a % MOD;
return ret * ret % MOD;
}
ll ncr(ll n, ll r){
return fact[n] * factINV[r] % MOD * factINV[n-r] % MOD;
}
int main(){
int n, m;
scanf("%d %d", &n, &m);
fact[0] = 1;
for (int i=1;i<=n*2;i++) fact[i] = fact[i-1] * i % MOD;
for (int i=0;i<=n*2;i++) factINV[i] = pw(fact[i], MOD-2);
dp[0][0] = 1;
int mx = 0;
for (int i=1;i<=m;i++){
int cnt = 0;
for (int j=i;j<=n*2;j+=m) cnt++;
int nxt = mx;
for (int j=0;j<=mx;j++){
for (int k=0;k*2<=cnt;k++){
nxt = max(nxt, j+k);
ll cost = fact[cnt] * factINV[cnt-k*2] % MOD;
cost = cost * pw(INV2, k) % MOD;
cost = cost * factINV[k] % MOD;
dp[i][j+k] = (dp[i][j+k] + dp[i-1][j] * cost) % MOD;
}
}
mx = nxt;
}
ll ans = fact[n*2];
for (int k=1;k<=mx;k++){
assert(k <= n);
ll cost = dp[m][k] * (ncr(n, k) * fact[k] % MOD * pw(2, k) % MOD) % MOD;
cost = cost * fact[n*2 - k*2] % MOD;
if (k%2==1) ans = (ans - cost + MOD) % MOD;
else ans = (ans + cost) % MOD;
}
printf("%lld\n", ans);
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
312 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
312 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
308 KB |
Output is correct |
| 11 |
Correct |
1 ms |
468 KB |
Output is correct |
| 12 |
Correct |
1 ms |
468 KB |
Output is correct |
| 13 |
Correct |
1 ms |
308 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
596 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
444 KB |
Output is correct |
| 18 |
Correct |
1 ms |
468 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
312 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
308 KB |
Output is correct |
| 11 |
Correct |
1 ms |
468 KB |
Output is correct |
| 12 |
Correct |
1 ms |
468 KB |
Output is correct |
| 13 |
Correct |
1 ms |
308 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
596 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
444 KB |
Output is correct |
| 18 |
Correct |
1 ms |
468 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
596 KB |
Output is correct |
| 22 |
Correct |
3 ms |
1620 KB |
Output is correct |
| 23 |
Correct |
1 ms |
312 KB |
Output is correct |
| 24 |
Correct |
2 ms |
980 KB |
Output is correct |
| 25 |
Correct |
2 ms |
1464 KB |
Output is correct |
| 26 |
Correct |
1 ms |
320 KB |
Output is correct |
| 27 |
Correct |
2 ms |
1876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
312 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
308 KB |
Output is correct |
| 11 |
Correct |
1 ms |
468 KB |
Output is correct |
| 12 |
Correct |
1 ms |
468 KB |
Output is correct |
| 13 |
Correct |
1 ms |
308 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
596 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
444 KB |
Output is correct |
| 18 |
Correct |
1 ms |
468 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
596 KB |
Output is correct |
| 22 |
Correct |
3 ms |
1620 KB |
Output is correct |
| 23 |
Correct |
1 ms |
312 KB |
Output is correct |
| 24 |
Correct |
2 ms |
980 KB |
Output is correct |
| 25 |
Correct |
2 ms |
1464 KB |
Output is correct |
| 26 |
Correct |
1 ms |
320 KB |
Output is correct |
| 27 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 28 |
Correct |
6 ms |
452 KB |
Output is correct |
| 29 |
Correct |
5 ms |
2464 KB |
Output is correct |
| 30 |
Correct |
5 ms |
3924 KB |
Output is correct |
| 31 |
Correct |
5 ms |
340 KB |
Output is correct |
| 32 |
Correct |
5 ms |
2620 KB |
Output is correct |
| 33 |
Correct |
6 ms |
4500 KB |
Output is correct |
| 34 |
Correct |
10 ms |
7124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
312 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
308 KB |
Output is correct |
| 11 |
Correct |
1 ms |
468 KB |
Output is correct |
| 12 |
Correct |
1 ms |
468 KB |
Output is correct |
| 13 |
Correct |
1 ms |
308 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
596 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
444 KB |
Output is correct |
| 18 |
Correct |
1 ms |
468 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
596 KB |
Output is correct |
| 22 |
Correct |
3 ms |
1620 KB |
Output is correct |
| 23 |
Correct |
1 ms |
312 KB |
Output is correct |
| 24 |
Correct |
2 ms |
980 KB |
Output is correct |
| 25 |
Correct |
2 ms |
1464 KB |
Output is correct |
| 26 |
Correct |
1 ms |
320 KB |
Output is correct |
| 27 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 28 |
Correct |
6 ms |
452 KB |
Output is correct |
| 29 |
Correct |
5 ms |
2464 KB |
Output is correct |
| 30 |
Correct |
5 ms |
3924 KB |
Output is correct |
| 31 |
Correct |
5 ms |
340 KB |
Output is correct |
| 32 |
Correct |
5 ms |
2620 KB |
Output is correct |
| 33 |
Correct |
6 ms |
4500 KB |
Output is correct |
| 34 |
Correct |
10 ms |
7124 KB |
Output is correct |
| 35 |
Correct |
36 ms |
468 KB |
Output is correct |
| 36 |
Correct |
29 ms |
18024 KB |
Output is correct |
| 37 |
Correct |
35 ms |
468 KB |
Output is correct |
| 38 |
Correct |
23 ms |
8816 KB |
Output is correct |
| 39 |
Correct |
31 ms |
15196 KB |
Output is correct |
| 40 |
Correct |
51 ms |
23000 KB |
Output is correct |
