QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#100273#6333. Festivals in JOI Kingdom 2zhouhuanyi51 2255ms238180kbC++231.8kb2023-04-25 14:08:052023-04-25 14:08:16

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-25 14:08:16]
  • 评测
  • 测评结果:51
  • 用时:2255ms
  • 内存:238180kb
  • [2023-04-25 14:08:05]
  • 提交

answer

#include<iostream>
#include<cstdio>
#define N 6000
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 n,mod,fac[N+1],invfac[N+1],C[N+1][N+1],dp[N+1][N+1],F[N+1][N+1],ans=1;
__int128 delta[N+1];
int MD(int x)
{
    return x>=mod?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 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 main()
{
    int s;
    n=read(),mod=read(),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) C[i][0]=1;
    for (int i=1;i<=N;++i)
	for (int j=1;j<=i;++j)
	    C[i][j]=MD(C[i-1][j-1]+C[i-1][j]);
    for (int i=0;i<=N;++i)
    {
	F[i][0]=1;
	for (int j=1;j<=N;++j) F[i][j]=1ll*F[i][j-1]*(i+j-1)%mod;
    }
    for (int i=1;i<=n;++i) ans=1ll*ans*((i<<1)-1)%mod;
    for (int i=2;i<=(n<<1);i+=2)
    {
	s=(i-2)>>1,Adder(dp[i][s+1],fac[s+1]);
	for (int j=2;j<=i-2;j+=2)
	{
	    for (int k=1;k<=i;++k) delta[k]=0;
	    for (int k=1;k<=j;++k)
		if (dp[j][k])
		{
		    s=(i-2-j)>>1;
		    for (int t=1;t<=s;++t) delta[t+1]+=(__int128)(dp[j][k])*F[j-k+1][s-t]*(k+1+s-t)*F[((s-t)<<1)+j+3][t-1];
		    Adder(dp[i][1],1ll*dp[j][k]*F[j-k+1][s]%mod);
		}
	    for (int k=1;k<=i;++k) Adder(dp[i][k],delta[k]%mod);
	}
    }
    for (int i=1;i<=(n<<1);++i) Adder2(ans,-dp[n<<1][i]);
    printf("%d\n",ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 501ms
memory: 236700kb

input:

1 194903119

output:

0

result:

ok 1 number(s): "0"

Test #2:

score: 0
Accepted
time: 490ms
memory: 236588kb

input:

2 933234047

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 497ms
memory: 236700kb

input:

3 277793111

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 495ms
memory: 236632kb

input:

4 355321177

output:

28

result:

ok 1 number(s): "28"

Test #5:

score: 0
Accepted
time: 492ms
memory: 236708kb

input:

5 306636893

output:

358

result:

ok 1 number(s): "358"

Subtask #2:

score: 5
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 5
Accepted
time: 489ms
memory: 236728kb

input:

8 361605653

output:

1236922

result:

ok 1 number(s): "1236922"

Test #7:

score: 0
Accepted
time: 503ms
memory: 236700kb

input:

8 995512643

output:

1236922

result:

ok 1 number(s): "1236922"

Test #8:

score: 0
Accepted
time: 435ms
memory: 236668kb

input:

8 101102801

output:

1236922

result:

ok 1 number(s): "1236922"

Test #9:

score: 0
Accepted
time: 486ms
memory: 236604kb

input:

6 458322727

output:

4894

result:

ok 1 number(s): "4894"

Test #10:

score: 0
Accepted
time: 486ms
memory: 236608kb

input:

7 721691819

output:

73884

result:

ok 1 number(s): "73884"

Test #11:

score: 0
Accepted
time: 484ms
memory: 236628kb

input:

7 370629137

output:

73884

result:

ok 1 number(s): "73884"

Subtask #3:

score: 27
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #12:

score: 27
Accepted
time: 486ms
memory: 236712kb

input:

30 779092367

output:

686412377

result:

ok 1 number(s): "686412377"

Test #13:

score: 0
Accepted
time: 498ms
memory: 236720kb

input:

29 963995171

output:

128570082

result:

ok 1 number(s): "128570082"

Test #14:

score: 0
Accepted
time: 503ms
memory: 236620kb

input:

18 666092701

output:

185922458

result:

ok 1 number(s): "185922458"

Test #15:

score: 0
Accepted
time: 453ms
memory: 236740kb

input:

14 671243719

output:

623913899

result:

ok 1 number(s): "623913899"

Subtask #4:

score: 14
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #16:

score: 14
Accepted
time: 2255ms
memory: 238180kb

input:

300 463478027

output:

89265245

result:

ok 1 number(s): "89265245"

Test #17:

score: 0
Accepted
time: 2158ms
memory: 238120kb

input:

296 567610679

output:

406342763

result:

ok 1 number(s): "406342763"

Test #18:

score: 0
Accepted
time: 2157ms
memory: 238160kb

input:

297 609090359

output:

128986577

result:

ok 1 number(s): "128986577"

Test #19:

score: 0
Accepted
time: 486ms
memory: 236908kb

input:

48 759569383

output:

635573072

result:

ok 1 number(s): "635573072"

Test #20:

score: 0
Accepted
time: 554ms
memory: 237012kb

input:

99 298873033

output:

285340078

result:

ok 1 number(s): "285340078"

Subtask #5:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #21:

score: 0
Time Limit Exceeded

input:

3000 752129633

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

0%