QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#301208#2811. NoMzhouhuanyi100 ✓32ms66372kbC++141.5kb2024-01-09 16:02:102024-01-09 16:02:10

Judging History

This is the latest submission verdict.

  • [2024-01-09 16:02:10]
  • Judged
  • Verdict: 100
  • Time: 32ms
  • Memory: 66372kb
  • [2024-01-09 16:02:10]
  • Submitted

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'