QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#301208 | #2811. NoM | zhouhuanyi | 100 ✓ | 32ms | 66372kb | C++14 | 1.5kb | 2024-01-09 16:02:10 | 2024-01-09 16:02:10 |
Judging History
answer
#include<iostream>
#include<cstdio>
#define N 4000
#define mod 1000000007
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int fast_pow(int a,int b)
{
int res=1,mul=a;
while (b)
{
if (b&1) res=1ll*res*mul%mod;
mul=1ll*mul*mul%mod,b>>=1;
}
return res;
}
int MD(int x)
{
return x>=mod?x-mod:x;
}
int MD2(int x)
{
return x<0?x+mod:x;
}
void Adder(int &x,int d)
{
x+=d;
if (x>=mod) x-=mod;
return;
}
void Adder2(int &x,int d)
{
x+=d;
if (x<0) x+=mod;
return;
}
int n,m,C[N+1][N+1],fac[N+1],invfac[N+1],cnt[N+1],dp[N+1],F[N+1],res,ans;
int main()
{
fac[0]=1;
for (int i=1;i<=N;++i) fac[i]=1ll*fac[i-1]*i%mod;
invfac[N]=fast_pow(fac[N],mod-2);
for (int i=N-1;i>=0;--i) invfac[i]=1ll*invfac[i+1]*(i+1)%mod;
for (int i=0;i<=N;++i)
for (int j=0;j<=i;++j)
C[i][j]=1ll*fac[i]*invfac[j]%mod*invfac[i-j]%mod;
n=read(),m=read();
for (int i=1;i<=(n<<1);++i) cnt[i%m]++;
dp[0]=1;
for (int i=0;i<m;++i)
{
for (int j=0;j<=res+(cnt[i]>>1);++j) F[j]=0;
for (int j=0;(j<<1)<=cnt[i];++j)
for (int k=0;k<=res;++k)
Adder(F[j+k],1ll*dp[k]*C[cnt[i]][j<<1]%mod*fac[j<<1]%mod*invfac[j]%mod);
res+=(cnt[i]>>1);
for (int j=0;j<=res;++j) dp[j]=F[j];
}
for (int i=0;i<=res;++i)
{
if (!(i&1)) Adder(ans,1ll*dp[i]*C[n][i]%mod*fac[i]%mod*fac[(n<<1)-(i<<1)]%mod);
else Adder2(ans,-1ll*dp[i]*C[n][i]%mod*fac[i]%mod*fac[(n<<1)-(i<<1)]%mod);
}
printf("%d\n",ans);
return 0;
}
详细
Subtask #1:
score: 9
Accepted
Test #1:
score: 9
Accepted
time: 12ms
memory: 65532kb
input:
1 1
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 14ms
memory: 66004kb
input:
2 1
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 12ms
memory: 65192kb
input:
2 2
output:
16
result:
ok single line: '16'
Test #4:
score: 0
Accepted
time: 8ms
memory: 65940kb
input:
3 1
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 7ms
memory: 65028kb
input:
3 2
output:
288
result:
ok single line: '288'
Test #6:
score: 0
Accepted
time: 23ms
memory: 65776kb
input:
3 3
output:
384
result:
ok single line: '384'
Test #7:
score: 0
Accepted
time: 18ms
memory: 65896kb
input:
4 2
output:
9216
result:
ok single line: '9216'
Test #8:
score: 0
Accepted
time: 25ms
memory: 66372kb
input:
4 3
output:
13824
result:
ok single line: '13824'
Test #9:
score: 0
Accepted
time: 16ms
memory: 66292kb
input:
5 1
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 23ms
memory: 65536kb
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: 12ms
memory: 66164kb
input:
99 55
output:
117836331
result:
ok single line: '117836331'
Test #12:
score: 0
Accepted
time: 25ms
memory: 66176kb
input:
69 50
output:
427094826
result:
ok single line: '427094826'
Test #13:
score: 0
Accepted
time: 7ms
memory: 65596kb
input:
67 5
output:
733227544
result:
ok single line: '733227544'
Test #14:
score: 0
Accepted
time: 16ms
memory: 65632kb
input:
69 26
output:
730153757
result:
ok single line: '730153757'
Test #15:
score: 0
Accepted
time: 12ms
memory: 65460kb
input:
71 64
output:
100578188
result:
ok single line: '100578188'
Test #16:
score: 0
Accepted
time: 15ms
memory: 66248kb
input:
87 10
output:
410973724
result:
ok single line: '410973724'
Test #17:
score: 0
Accepted
time: 20ms
memory: 65752kb
input:
64 35
output:
623989218
result:
ok single line: '623989218'
Test #18:
score: 0
Accepted
time: 11ms
memory: 65820kb
input:
67 51
output:
312068739
result:
ok single line: '312068739'
Test #19:
score: 0
Accepted
time: 20ms
memory: 65592kb
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: 8ms
memory: 66168kb
input:
164 20
output:
152386555
result:
ok single line: '152386555'
Test #21:
score: 0
Accepted
time: 14ms
memory: 65104kb
input:
154 80
output:
741601266
result:
ok single line: '741601266'
Test #22:
score: 0
Accepted
time: 25ms
memory: 65196kb
input:
266 255
output:
245915928
result:
ok single line: '245915928'
Test #23:
score: 0
Accepted
time: 29ms
memory: 66220kb
input:
239 19
output:
511848592
result:
ok single line: '511848592'
Test #24:
score: 0
Accepted
time: 15ms
memory: 66132kb
input:
296 141
output:
462138216
result:
ok single line: '462138216'
Test #25:
score: 0
Accepted
time: 14ms
memory: 65528kb
input:
255 250
output:
727256255
result:
ok single line: '727256255'
Test #26:
score: 0
Accepted
time: 17ms
memory: 65436kb
input:
257 15
output:
253032679
result:
ok single line: '253032679'
Test #27:
score: 0
Accepted
time: 25ms
memory: 66128kb
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: 18ms
memory: 65592kb
input:
625 19
output:
787742499
result:
ok single line: '787742499'
Test #29:
score: 0
Accepted
time: 4ms
memory: 66140kb
input:
657 324
output:
660247748
result:
ok single line: '660247748'
Test #30:
score: 0
Accepted
time: 4ms
memory: 65648kb
input:
646 582
output:
830442831
result:
ok single line: '830442831'
Test #31:
score: 0
Accepted
time: 15ms
memory: 66360kb
input:
637 14
output:
468904506
result:
ok single line: '468904506'
Test #32:
score: 0
Accepted
time: 19ms
memory: 66320kb
input:
685 343
output:
516203560
result:
ok single line: '516203560'
Test #33:
score: 0
Accepted
time: 24ms
memory: 65756kb
input:
713 644
output:
225559251
result:
ok single line: '225559251'
Test #34:
score: 0
Accepted
time: 16ms
memory: 65652kb
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: 19ms
memory: 65692kb
input:
1624 18
output:
887332511
result:
ok single line: '887332511'
Test #36:
score: 0
Accepted
time: 32ms
memory: 65484kb
input:
1779 1687
output:
611283083
result:
ok single line: '611283083'
Test #37:
score: 0
Accepted
time: 28ms
memory: 65652kb
input:
1603 18
output:
846564825
result:
ok single line: '846564825'
Test #38:
score: 0
Accepted
time: 23ms
memory: 66240kb
input:
1651 818
output:
148850576
result:
ok single line: '148850576'
Test #39:
score: 0
Accepted
time: 25ms
memory: 65568kb
input:
1579 1501
output:
427262684
result:
ok single line: '427262684'
Test #40:
score: 0
Accepted
time: 31ms
memory: 65736kb
input:
2000 1999
output:
510859110
result:
ok single line: '510859110'