QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276525#7609. ColonizationAllTheWayNorth#WA 1ms3948kbC++172.9kb2023-12-05 22:24:432023-12-05 22:24:43

Judging History

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

  • [2023-12-05 22:24:43]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3948kb
  • [2023-12-05 22:24:43]
  • 提交

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],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]);
			}
			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]);
		}
	}
	// 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));
		}
	}
	for(int i=B;i>=1;i--) ans[i]=mod(ans[i]+cys-ans[i-1]);
	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: 3856kb

input:

3 100000007

output:

1 0 0 

result:

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

Test #2:

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

input:

6 300000007

output:

1 5 0 0 0 0 

result:

ok 6 numbers

Test #3:

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

input:

10 1000000007

output:

1 104 1 0 0 0 0 0 0 0 

result:

ok 10 numbers

Test #4:

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

input:

2 739878731

output:

1 0 

result:

ok 2 number(s): "1 0"

Test #5:

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

input:

3 122646779

output:

1 0 0 

result:

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

Test #6:

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

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: 3764kb

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: 3772kb

input:

6 1000000007

output:

1 5 0 0 0 0 

result:

ok 6 numbers

Test #9:

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

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: 3856kb

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: 3836kb

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: 3828kb

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: 3784kb

input:

13 1000000007

output:

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

result:

ok 13 numbers

Test #15:

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

input:

14 1000000007

output:

1 2870 288 0 0 0 0 0 0 0 0 0 0 0 

result:

wrong answer 2nd numbers differ - expected: '2871', found: '2870'