QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276563#7609. ColonizationAllTheWayNorth#WA 1ms3944kbC++173.4kb2023-12-05 22:47:172023-12-05 22:47:18

Judging History

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

  • [2023-12-05 22:47:18]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3944kb
  • [2023-12-05 22:47:17]
  • 提交

answer

#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;

template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int B=10;
int n,cys;
ll f[505][15],d[505][15],ansf[505][15],ansd[505][15],ans[505],ansh[505],h[505][15],g[505][15],fac[505],inv[505];

ll mod(ll x){return x>=cys?x-cys:x;}

ll qpow(ll x,ll p){
	ll ret=1;
	for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys;
	return ret;
}

ll C(ll x,ll y){
	ll ret=1;
	for(int i=1;i<=y;i++) ret=ret*mod(x+cys-i+1)%cys;
	return ret*inv[y]%cys;
}

int main(){
	n=readint(); cys=readint();
	fac[0]=inv[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%cys;
	inv[n]=qpow(fac[n],cys-2);
	for(int i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%cys;
	for(int i=0;i<=B;i++) f[0][i]=d[0][i]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=B;j++){
			for(int k=0;k<i;k++){
				d[i][j]=(d[i][j]+f[i-k-1][j-1]*mod(d[k][j]+cys-d[k][j-1]))%cys;
				if(!k) d[i][j]=mod(d[i][j]+f[i-k-1][j-1]);
				h[i][j]=(h[i][j]+f[i-k-1][j-1]*h[k][j])%cys;
				h[i][j]=(h[i][j]+f[i-k-1][j-1]*g[k][j])%cys;
			}
			for(int k=1;k<i&&i+k<=n;k++) g[i+k][j]=(g[i+k][j]+mod(d[i][j]+cys-d[i][j-1])*mod(d[k][j]+cys-d[k][j-1]))%cys;
			if(i+i<=n) g[i+i][j]=mod(g[i+i][j]+C(mod(d[i][j]+cys-d[i][j-1])+1,2));
			for(int k=n;k>=0;k--){
				for(int l=j;l<=B;l++){
					ll tmp=1,val=mod(d[i][j]+cys-d[i][j-1]);
					for(int t=1;k+t*i<=n;t++){
						tmp=tmp*(val+t-1)%cys;
						f[k+t*i][l]=(f[k+t*i][l]+f[k][l]*tmp%cys*inv[t])%cys;
					}
				}
			}
		}
		// for(int j=1;j<=B;j++) cout<<'('<<d[i][j]<<' '<<f[i][j]<<") ";
		// cout<<endl;
	}
	for(int i=0;i<=B;i++) ansf[0][i]=1;
	for(int i=1;i<=(n-1)/2;i++){
		for(int j=1;j<=B;j++){
			for(int k=n;k>=0;k--){
				for(int l=j;l<=B;l++){
					ll tmp=1,val=mod(d[i][j]+cys-d[i][j-1]);
					for(int t=1;k+t*i<=n;t++){
						tmp=tmp*(val+t-1)%cys;
						ansf[k+t*i][l]=(ansf[k+t*i][l]+ansf[k][l]*tmp%cys*inv[t])%cys;
					}
				}
			}
		}
	}
	for(int i=1;i<=(n-1)/2;i++){
		for(int j=i;j<=(n-1)/2;j++){
			for(int k=1;k<=B;k++){
				if(i!=j) ansd[i+j][k]=(ansd[i+j][k]+mod(d[i][k]+cys-d[i][k-1])*mod(d[j][k]+cys-d[j][k-1]))%cys;
				else ansd[i+j][k]=mod(ansd[i+j][k]+C(mod(d[i][k]+cys-d[i][k-1])+1,2));
			}
		}
	}
	for(int i=1;i<=(n-1)/2;i++)
		for(int j=1;j<=B;j++)
			ansd[i][j]=mod(ansd[i][j]+mod(d[i][j]+cys-d[i][j-1]))%cys;
	for(int i=1;i<=B;i++){
		for(int k=0;k<n;k++){
			ans[i]=(ans[i]+ansf[n-k-1][i-1]*ansd[k][i])%cys;
			if(!k) ans[i]=mod(ans[i]+ansf[n-k-1][i-1]);
			if(k&&k<=(n-1)/2) ansh[i]=(ansh[i]+ansf[n-k-1][i-1]*h[k][i])%cys;
		}
	}
	// for(int i=1;i<=n;i++){
	// 	for(int j=1;j<=B;j++) cout<<ansd[i][j]<<' ';
	// 	cout<<endl;
	// }
	if(n%2==0){
		for(int i=1;i<=B;i++){
			ans[i]=mod(ans[i]+C(d[n/2][i]+1,2));
			ansh[i]=mod(ansh[i]+d[n/2][i-1]*h[n/2][i])%cys;
		}
	}
	for(int i=B;i>=1;i--) ans[i]=mod(ans[i]+cys-ans[i-1]);
	for(int i=1;i<=B;i++) ans[i]=mod(ans[i]+ansh[i]),ans[i+1]=mod(ans[i+1]+cys-ansh[i]);
	for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
	printf("\n");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3808kb

input:

3 100000007

output:

1 0 0 

result:

ok 3 number(s): "1 0 0"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

6 300000007

output:

1 5 0 0 0 0 

result:

ok 6 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 3860kb

input:

10 1000000007

output:

1 104 1 0 0 0 0 0 0 0 

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 3852kb

input:

2 739878731

output:

1 0 

result:

ok 2 number(s): "1 0"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

3 122646779

output:

1 0 0 

result:

ok 3 number(s): "1 0 0"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

4 457287433

output:

1 1 0 0 

result:

ok 4 number(s): "1 1 0 0"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

5 1000000007

output:

1 2 0 0 0 

result:

ok 5 number(s): "1 2 0 0 0"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

6 1000000007

output:

1 5 0 0 0 0 

result:

ok 6 numbers

Test #9:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

7 763596907

output:

1 10 0 0 0 0 0 

result:

ok 7 numbers

Test #10:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

8 1000000007

output:

1 22 0 0 0 0 0 0 

result:

ok 8 numbers

Test #11:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

9 729507523

output:

1 46 0 0 0 0 0 0 0 

result:

ok 9 numbers

Test #12:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

11 488473873

output:

1 230 4 0 0 0 0 0 0 0 0 

result:

ok 11 numbers

Test #13:

score: 0
Accepted
time: 1ms
memory: 3856kb

input:

12 100000007

output:

1 531 19 0 0 0 0 0 0 0 0 0 

result:

ok 12 numbers

Test #14:

score: 0
Accepted
time: 1ms
memory: 3936kb

input:

13 1000000007

output:

1 1223 77 0 0 0 0 0 0 0 0 0 0 

result:

ok 13 numbers

Test #15:

score: 0
Accepted
time: 1ms
memory: 3940kb

input:

14 1000000007

output:

1 2871 287 0 0 0 0 0 0 0 0 0 0 0 

result:

ok 14 numbers

Test #16:

score: -100
Wrong Answer
time: 1ms
memory: 3944kb

input:

15 290707159

output:

1 6752 988 0 0 0 0 0 0 0 0 0 0 0 0 

result:

wrong answer 2nd numbers differ - expected: '6738', found: '6752'