QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#425652 | #2811. NoM | ship2077 | 100 ✓ | 17ms | 4020kb | C++14 | 1.2kb | 2024-05-30 15:20:36 | 2024-05-30 15:20:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int M=2005,mod=1e9+7;
int n,m,N;long long ans;
int f[M],g[M],pw[M],fac[M],ifac[M],coef[M];
int qpow(int x,int n){
int s=1; while (n){
if (n&1) s=1ll*s*x%mod;
x=1ll*x*x%mod; n>>=1;
} return s;
}
int rdc(int x){return x>=mod?x-mod:x;}
void init(){
for (int i=pw[0]=1;i<=n;i++) pw[i]=rdc(pw[i-1]<<1);
for (int i=fac[0]=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
ifac[n]=qpow(fac[n],mod-2);
for (int i=n;i;i--) ifac[i-1]=1ll*ifac[i]*i%mod;
for (int i=coef[0]=1;i<=n;i++) coef[i]=1ll*coef[i-1]*(i*2-1)%mod;
}
int c(int n,int m){return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
int main(){
scanf("%d%d",&n,&m);
init();f[0]=1;N=n<<1;
for (int i=0,sum=0;i<m;i++){
int len=i<N%m?N/m+1:N/m;
for (int j=0;j<=sum;j++) g[j]=f[j],f[j]=0;
for (int j=0;j<=sum;j++)
for (int k=0;k*2<=len;k++)
f[j+k]=(f[j+k]+1ll*g[j]*coef[k]%mod*c(len,k<<1))%mod;
sum+=len>>1;
}
for (int i=0;i<=n;i++){
int rec=1ll*f[i]*coef[n-i]%mod;
ans+=i&1?-rec:rec;
}
ans%=mod;if (ans<0) ans+=mod;
printf("%d\n",1ll*ans*fac[n]%mod*pw[n]%mod);
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: 3952kb
input:
1 1
output:
0
result:
ok single line: '0'
Test #2:
score: 9
Accepted
time: 1ms
memory: 3816kb
input:
2 1
output:
0
result:
ok single line: '0'
Test #3:
score: 9
Accepted
time: 1ms
memory: 3812kb
input:
2 2
output:
16
result:
ok single line: '16'
Test #4:
score: 9
Accepted
time: 1ms
memory: 3808kb
input:
3 1
output:
0
result:
ok single line: '0'
Test #5:
score: 9
Accepted
time: 1ms
memory: 3952kb
input:
3 2
output:
288
result:
ok single line: '288'
Test #6:
score: 9
Accepted
time: 1ms
memory: 3996kb
input:
3 3
output:
384
result:
ok single line: '384'
Test #7:
score: 9
Accepted
time: 1ms
memory: 3808kb
input:
4 2
output:
9216
result:
ok single line: '9216'
Test #8:
score: 9
Accepted
time: 1ms
memory: 3996kb
input:
4 3
output:
13824
result:
ok single line: '13824'
Test #9:
score: 9
Accepted
time: 1ms
memory: 3996kb
input:
5 1
output:
0
result:
ok single line: '0'
Test #10:
score: 9
Accepted
time: 1ms
memory: 3952kb
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: 0ms
memory: 3972kb
input:
99 55
output:
117836331
result:
ok single line: '117836331'
Test #12:
score: 12
Accepted
time: 1ms
memory: 3964kb
input:
69 50
output:
427094826
result:
ok single line: '427094826'
Test #13:
score: 12
Accepted
time: 1ms
memory: 3960kb
input:
67 5
output:
733227544
result:
ok single line: '733227544'
Test #14:
score: 12
Accepted
time: 1ms
memory: 3868kb
input:
69 26
output:
730153757
result:
ok single line: '730153757'
Test #15:
score: 12
Accepted
time: 1ms
memory: 3960kb
input:
71 64
output:
100578188
result:
ok single line: '100578188'
Test #16:
score: 12
Accepted
time: 1ms
memory: 3936kb
input:
87 10
output:
410973724
result:
ok single line: '410973724'
Test #17:
score: 12
Accepted
time: 1ms
memory: 3820kb
input:
64 35
output:
623989218
result:
ok single line: '623989218'
Test #18:
score: 12
Accepted
time: 1ms
memory: 3948kb
input:
67 51
output:
312068739
result:
ok single line: '312068739'
Test #19:
score: 12
Accepted
time: 1ms
memory: 3960kb
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: 0ms
memory: 3968kb
input:
164 20
output:
152386555
result:
ok single line: '152386555'
Test #21:
score: 13
Accepted
time: 1ms
memory: 3956kb
input:
154 80
output:
741601266
result:
ok single line: '741601266'
Test #22:
score: 13
Accepted
time: 1ms
memory: 3888kb
input:
266 255
output:
245915928
result:
ok single line: '245915928'
Test #23:
score: 13
Accepted
time: 0ms
memory: 3956kb
input:
239 19
output:
511848592
result:
ok single line: '511848592'
Test #24:
score: 13
Accepted
time: 1ms
memory: 3976kb
input:
296 141
output:
462138216
result:
ok single line: '462138216'
Test #25:
score: 13
Accepted
time: 1ms
memory: 4016kb
input:
255 250
output:
727256255
result:
ok single line: '727256255'
Test #26:
score: 13
Accepted
time: 1ms
memory: 3884kb
input:
257 15
output:
253032679
result:
ok single line: '253032679'
Test #27:
score: 13
Accepted
time: 1ms
memory: 3972kb
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: 2ms
memory: 3832kb
input:
625 19
output:
787742499
result:
ok single line: '787742499'
Test #29:
score: 18
Accepted
time: 2ms
memory: 3872kb
input:
657 324
output:
660247748
result:
ok single line: '660247748'
Test #30:
score: 18
Accepted
time: 2ms
memory: 3872kb
input:
646 582
output:
830442831
result:
ok single line: '830442831'
Test #31:
score: 18
Accepted
time: 2ms
memory: 3976kb
input:
637 14
output:
468904506
result:
ok single line: '468904506'
Test #32:
score: 18
Accepted
time: 2ms
memory: 3912kb
input:
685 343
output:
516203560
result:
ok single line: '516203560'
Test #33:
score: 18
Accepted
time: 3ms
memory: 3888kb
input:
713 644
output:
225559251
result:
ok single line: '225559251'
Test #34:
score: 18
Accepted
time: 5ms
memory: 4020kb
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: 3ms
memory: 3880kb
input:
1624 18
output:
887332511
result:
ok single line: '887332511'
Test #36:
score: 48
Accepted
time: 15ms
memory: 3952kb
input:
1779 1687
output:
611283083
result:
ok single line: '611283083'
Test #37:
score: 48
Accepted
time: 6ms
memory: 3972kb
input:
1603 18
output:
846564825
result:
ok single line: '846564825'
Test #38:
score: 48
Accepted
time: 7ms
memory: 3952kb
input:
1651 818
output:
148850576
result:
ok single line: '148850576'
Test #39:
score: 48
Accepted
time: 12ms
memory: 3916kb
input:
1579 1501
output:
427262684
result:
ok single line: '427262684'
Test #40:
score: 48
Accepted
time: 17ms
memory: 3956kb
input:
2000 1999
output:
510859110
result:
ok single line: '510859110'