QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#276525 | #7609. Colonization | AllTheWayNorth# | WA | 1ms | 3948kb | C++17 | 2.9kb | 2023-12-05 22:24:43 | 2023-12-05 22:24:43 |
Judging History
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'