QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#778098 | #2811. NoM | ChiFAN | 100 ✓ | 24ms | 3740kb | C++14 | 1.2kb | 2024-11-24 12:38:50 | 2024-11-24 12:38:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
const int maxn = 4e3+114;
int fac[maxn],inv[maxn];
int iv[maxn];
int qpow(int a,int b){
if(b==0) return 1;
if(b==1) return a;
int res=qpow(a,b/2);
res=res*res%mod;
if(b%2==1) res=res*a%mod;
return res;
}
int dp[maxn];//全局选取 j 对的方案
int C(int n,int m){
if(n<m) return 0;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int n,m,ans;
signed main(){
fac[0]=inv[0]=1;
for(int i=1;i<maxn;i++) fac[i]=fac[i-1]*i%mod,inv[i]=qpow(fac[i],mod-2);
cin>>n>>m;
n*=2;
ans=C(n,n/2)*fac[n/2]%mod;
if(n<=m){
cout<<ans*fac[n/2]%mod<<'\n';
return 0;
}
dp[0]=1;
int sum=0;
for(int p=0;p<m;p++){
int cnt=(n-p)/m+(p==0?0:1);
for(int i=sum;i>=0;i--){
for(int j=1;j*2<=cnt;j++) dp[i+j]=(dp[i+j]+dp[i]*C(cnt,j*2)%mod*C(j*2,j)%mod*fac[j]%mod)%mod;
}
sum+=(cnt/2);
}
for(int j=1;j<=sum;j++){
if(n-2*j!=0) dp[j]=dp[j]*C(n-2*j,(n-2*j)/2)%mod*fac[(n-2*j)/2]%mod;
ans=(ans+dp[j]*(j%2==0?1:(mod-1))%mod)%mod;
}
cout<<ans*fac[n/2]%mod<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 9
Accepted
Test #1:
score: 9
Accepted
time: 1ms
memory: 3644kb
input:
1 1
output:
0
result:
ok single line: '0'
Test #2:
score: 9
Accepted
time: 1ms
memory: 3572kb
input:
2 1
output:
0
result:
ok single line: '0'
Test #3:
score: 9
Accepted
time: 1ms
memory: 3584kb
input:
2 2
output:
16
result:
ok single line: '16'
Test #4:
score: 9
Accepted
time: 0ms
memory: 3644kb
input:
3 1
output:
0
result:
ok single line: '0'
Test #5:
score: 9
Accepted
time: 1ms
memory: 3648kb
input:
3 2
output:
288
result:
ok single line: '288'
Test #6:
score: 9
Accepted
time: 1ms
memory: 3724kb
input:
3 3
output:
384
result:
ok single line: '384'
Test #7:
score: 9
Accepted
time: 1ms
memory: 3704kb
input:
4 2
output:
9216
result:
ok single line: '9216'
Test #8:
score: 9
Accepted
time: 1ms
memory: 3668kb
input:
4 3
output:
13824
result:
ok single line: '13824'
Test #9:
score: 9
Accepted
time: 1ms
memory: 3708kb
input:
5 1
output:
0
result:
ok single line: '0'
Test #10:
score: 9
Accepted
time: 0ms
memory: 3644kb
input:
5 5
output:
2088960
result:
ok single line: '2088960'
Subtask #2:
score: 12
Accepted
Dependency #1:
100%
Accepted
Test #11:
score: 12
Accepted
time: 1ms
memory: 3524kb
input:
99 55
output:
117836331
result:
ok single line: '117836331'
Test #12:
score: 12
Accepted
time: 2ms
memory: 3584kb
input:
69 50
output:
427094826
result:
ok single line: '427094826'
Test #13:
score: 12
Accepted
time: 1ms
memory: 3740kb
input:
67 5
output:
733227544
result:
ok single line: '733227544'
Test #14:
score: 12
Accepted
time: 1ms
memory: 3740kb
input:
69 26
output:
730153757
result:
ok single line: '730153757'
Test #15:
score: 12
Accepted
time: 1ms
memory: 3720kb
input:
71 64
output:
100578188
result:
ok single line: '100578188'
Test #16:
score: 12
Accepted
time: 1ms
memory: 3724kb
input:
87 10
output:
410973724
result:
ok single line: '410973724'
Test #17:
score: 12
Accepted
time: 1ms
memory: 3708kb
input:
64 35
output:
623989218
result:
ok single line: '623989218'
Test #18:
score: 12
Accepted
time: 1ms
memory: 3568kb
input:
67 51
output:
312068739
result:
ok single line: '312068739'
Test #19:
score: 12
Accepted
time: 1ms
memory: 3672kb
input:
85 3
output:
796582412
result:
ok single line: '796582412'
Subtask #3:
score: 13
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #20:
score: 13
Accepted
time: 1ms
memory: 3664kb
input:
164 20
output:
152386555
result:
ok single line: '152386555'
Test #21:
score: 13
Accepted
time: 1ms
memory: 3528kb
input:
154 80
output:
741601266
result:
ok single line: '741601266'
Test #22:
score: 13
Accepted
time: 2ms
memory: 3704kb
input:
266 255
output:
245915928
result:
ok single line: '245915928'
Test #23:
score: 13
Accepted
time: 1ms
memory: 3736kb
input:
239 19
output:
511848592
result:
ok single line: '511848592'
Test #24:
score: 13
Accepted
time: 2ms
memory: 3640kb
input:
296 141
output:
462138216
result:
ok single line: '462138216'
Test #25:
score: 13
Accepted
time: 0ms
memory: 3644kb
input:
255 250
output:
727256255
result:
ok single line: '727256255'
Test #26:
score: 13
Accepted
time: 0ms
memory: 3668kb
input:
257 15
output:
253032679
result:
ok single line: '253032679'
Test #27:
score: 13
Accepted
time: 0ms
memory: 3636kb
input:
300 299
output:
559277735
result:
ok single line: '559277735'
Subtask #4:
score: 18
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #28:
score: 18
Accepted
time: 3ms
memory: 3644kb
input:
625 19
output:
787742499
result:
ok single line: '787742499'
Test #29:
score: 18
Accepted
time: 4ms
memory: 3640kb
input:
657 324
output:
660247748
result:
ok single line: '660247748'
Test #30:
score: 18
Accepted
time: 3ms
memory: 3604kb
input:
646 582
output:
830442831
result:
ok single line: '830442831'
Test #31:
score: 18
Accepted
time: 3ms
memory: 3712kb
input:
637 14
output:
468904506
result:
ok single line: '468904506'
Test #32:
score: 18
Accepted
time: 4ms
memory: 3720kb
input:
685 343
output:
516203560
result:
ok single line: '516203560'
Test #33:
score: 18
Accepted
time: 4ms
memory: 3572kb
input:
713 644
output:
225559251
result:
ok single line: '225559251'
Test #34:
score: 18
Accepted
time: 3ms
memory: 3648kb
input:
900 899
output:
941929065
result:
ok single line: '941929065'
Subtask #5:
score: 48
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #35:
score: 48
Accepted
time: 15ms
memory: 3724kb
input:
1624 18
output:
887332511
result:
ok single line: '887332511'
Test #36:
score: 48
Accepted
time: 17ms
memory: 3648kb
input:
1779 1687
output:
611283083
result:
ok single line: '611283083'
Test #37:
score: 48
Accepted
time: 15ms
memory: 3596kb
input:
1603 18
output:
846564825
result:
ok single line: '846564825'
Test #38:
score: 48
Accepted
time: 16ms
memory: 3720kb
input:
1651 818
output:
148850576
result:
ok single line: '148850576'
Test #39:
score: 48
Accepted
time: 14ms
memory: 3596kb
input:
1579 1501
output:
427262684
result:
ok single line: '427262684'
Test #40:
score: 48
Accepted
time: 24ms
memory: 3724kb
input:
2000 1999
output:
510859110
result:
ok single line: '510859110'