| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 786483 |
2023-07-18T08:17:06 Z |
반딧불(#10026) |
NoM (RMI21_nom) |
C++17 |
|
76 ms |
101708 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
ll mpow(ll x, ll y){
if(!y) return 1;
if(y&1) return mpow(x, y-1) * x % MOD;
ll tmp = mpow(x, y>>1);
return tmp*tmp%MOD;
}
int n, m;
int a, al, b, bl, as, bs;
ll linkCnt[2002]; /// linkCnt[i]: 2i������ ���� ����� ��
ll comb[4002][4002];
ll fact[4002];
ll ans;
ll DPa[4002][4002]; /// DPa[i][j]: i���� a���� ���� ����� j���� ���� �̴� ����� ��
ll DPb[4002][4002]; /// DPa[i][j]: i���� a���� ���� ����� j���� ���� �̴� ����� ��
int main(){
scanf("%d %d", &n, &m);
m = min(m, n*2);
a = (n+n)/m, b = a+1;
bl = (n+n)%m, al=m-bl;
as = a*al, bs = b*bl;
for(int i=0; i<=n+n; i++){
comb[i][0] = comb[i][i] = 1;
for(int j=1; j<i; j++) comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % MOD;
}
fact[0] = 1;
for(int i=1; i<=n+n; i++) fact[i] = fact[i-1] * i % MOD;
linkCnt[0] = 1;
for(int i=1; i<=n; i++) linkCnt[i] = linkCnt[i-1] * (i+i-1) % MOD;
for(int i=0; i<=n; i++) linkCnt[i] = linkCnt[i] * fact[i] % MOD;
/// a al������ Ž��
DPa[0][0] = 1;
for(int i=1; i<=al; i++){
for(int j=0; j*2<=as; j++){
if(!DPa[i-1][j]) continue;
ll v = 1;
for(int k=j; (k-j)*2 <= a && k*2<=as; k++){
DPa[i][k] = (DPa[i][k] + DPa[i-1][j] * v % MOD * comb[k][j]) % MOD;
v *= comb[a-(k-j)*2][2];
v %= MOD;
}
}
}
/// b bl������ Ž��
DPb[0][0] = 1;
for(int i=1; i<=bl; i++){
for(int j=0; j*2<=bs; j++){
if(!DPb[i-1][j]) continue;
ll v = 1;
for(int k=j; (k-j)*2 <= b && k*2<=bs; k++){
DPb[i][k] = (DPb[i][k] + DPb[i-1][j] * v % MOD * comb[k][j]) % MOD;
v *= comb[b-(k-j)*2][2];
v %= MOD;
}
}
}
for(int i=0; i*2<=as; i++){
for(int j=0; j*2<=bs; j++){
ll v = DPa[al][i] * DPb[bl][j] % MOD * linkCnt[n-i-j] % MOD * comb[n][i] % MOD * comb[n-i][j] % MOD;
if((i+j)&1) ans = (ans - v + MOD) % MOD;
else ans = (ans + v) % MOD;
}
}
for(int i=0; i<n; i++) ans = (ans * 2) % MOD;
printf("%lld", ans);
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
26 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
292 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
292 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 13 |
Correct |
1 ms |
852 KB |
Output is correct |
| 14 |
Correct |
1 ms |
980 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1216 KB |
Output is correct |
| 17 |
Correct |
1 ms |
980 KB |
Output is correct |
| 18 |
Correct |
1 ms |
1076 KB |
Output is correct |
| 19 |
Correct |
1 ms |
1108 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
292 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 13 |
Correct |
1 ms |
852 KB |
Output is correct |
| 14 |
Correct |
1 ms |
980 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1216 KB |
Output is correct |
| 17 |
Correct |
1 ms |
980 KB |
Output is correct |
| 18 |
Correct |
1 ms |
1076 KB |
Output is correct |
| 19 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2132 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2232 KB |
Output is correct |
| 22 |
Correct |
3 ms |
4820 KB |
Output is correct |
| 23 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 24 |
Correct |
3 ms |
4692 KB |
Output is correct |
| 25 |
Correct |
3 ms |
4620 KB |
Output is correct |
| 26 |
Correct |
2 ms |
3512 KB |
Output is correct |
| 27 |
Correct |
4 ms |
5716 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
292 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 13 |
Correct |
1 ms |
852 KB |
Output is correct |
| 14 |
Correct |
1 ms |
980 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1216 KB |
Output is correct |
| 17 |
Correct |
1 ms |
980 KB |
Output is correct |
| 18 |
Correct |
1 ms |
1076 KB |
Output is correct |
| 19 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2132 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2232 KB |
Output is correct |
| 22 |
Correct |
3 ms |
4820 KB |
Output is correct |
| 23 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 24 |
Correct |
3 ms |
4692 KB |
Output is correct |
| 25 |
Correct |
3 ms |
4620 KB |
Output is correct |
| 26 |
Correct |
2 ms |
3512 KB |
Output is correct |
| 27 |
Correct |
4 ms |
5716 KB |
Output is correct |
| 28 |
Correct |
7 ms |
11604 KB |
Output is correct |
| 29 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 30 |
Correct |
14 ms |
15320 KB |
Output is correct |
| 31 |
Correct |
9 ms |
11964 KB |
Output is correct |
| 32 |
Correct |
9 ms |
15572 KB |
Output is correct |
| 33 |
Correct |
13 ms |
17788 KB |
Output is correct |
| 34 |
Correct |
19 ms |
27060 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
292 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 13 |
Correct |
1 ms |
852 KB |
Output is correct |
| 14 |
Correct |
1 ms |
980 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1216 KB |
Output is correct |
| 17 |
Correct |
1 ms |
980 KB |
Output is correct |
| 18 |
Correct |
1 ms |
1076 KB |
Output is correct |
| 19 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2132 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2232 KB |
Output is correct |
| 22 |
Correct |
3 ms |
4820 KB |
Output is correct |
| 23 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 24 |
Correct |
3 ms |
4692 KB |
Output is correct |
| 25 |
Correct |
3 ms |
4620 KB |
Output is correct |
| 26 |
Correct |
2 ms |
3512 KB |
Output is correct |
| 27 |
Correct |
4 ms |
5716 KB |
Output is correct |
| 28 |
Correct |
7 ms |
11604 KB |
Output is correct |
| 29 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 30 |
Correct |
14 ms |
15320 KB |
Output is correct |
| 31 |
Correct |
9 ms |
11964 KB |
Output is correct |
| 32 |
Correct |
9 ms |
15572 KB |
Output is correct |
| 33 |
Correct |
13 ms |
17788 KB |
Output is correct |
| 34 |
Correct |
19 ms |
27060 KB |
Output is correct |
| 35 |
Correct |
38 ms |
54836 KB |
Output is correct |
| 36 |
Correct |
56 ms |
79984 KB |
Output is correct |
| 37 |
Correct |
43 ms |
53628 KB |
Output is correct |
| 38 |
Correct |
44 ms |
64524 KB |
Output is correct |
| 39 |
Correct |
46 ms |
65324 KB |
Output is correct |
| 40 |
Correct |
76 ms |
101708 KB |
Output is correct |
