QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#299168 | #7644. Good Splits | ucup-team1525 | WA | 1ms | 5772kb | C++17 | 2.0kb | 2024-01-06 17:29:59 | 2024-01-06 17:30:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=200;
int mod;
int add(int x,int y){ return (x+=y)>=mod?x-mod:x; }
int sub(int x,int y){ return (x-=y)<0?x+mod:x; }
void inc(int &x,int y){ if((x+=y)>=mod) x-=mod; }
int n;
int dp[N*2+5][N+5][N+5];
int g[N+5];
int pf[N+5];
int f[N+5],h[N*2+5][N+5];
int C[N*2+5][N*2+5];
int ans[N+5];
int main(){
scanf("%d %d",&n,&mod);
C[0][0]=1;
for(int i=1;i<=n*2;i++){
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++)
C[i][j]=add(C[i-1][j],C[i-1][j-1]);
}
dp[0][0][0]=1;
for(int i=0;i<n*2;i++){
for(int j=0;j<=min(i,n);j++)
for(int k=0;k<=min(i,n);k++){
int w=dp[i][j][k];
inc(dp[i+1][j+1][k],w);
inc(dp[i+1][j][k+1],w);
if(j) inc(dp[i+1][j-1][k],w);
if(k) inc(dp[i+1][j][k-1],w);
}
}
for(int i=0;i<=n;i++) g[i]=dp[i*2][0][0];
for(int i=1;i<=n;i++)
printf("%d ",g[i]);
puts("");
h[0][0]=1;
for(int i=1;i<=n*2;i++)
for(int j=n;j>=0;j--)
for(int k=0;k<=j;k++)
h[i][j]=(h[i][j]+1ll*h[i-1][j-k]*g[k])%mod;
f[0]=1;
for(int i=1;i<=n;i++){
f[i]=g[i];
for(int j=0;j<i;j++){
f[i]=(f[i]-1ll*f[j]*h[2*j][i-j])%mod;
// printf("%d %d %d\n",i,j,h[2*j][i-j]);
}
if(f[i]<0) f[i]+=mod;
}
for(int i=1;i<=n;i++) f[i]=1ll*f[i]*(mod+1)/2%mod;
memset(h,0,sizeof h);
for(int i=0;i<=n*2;i++)
h[i][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++)
ans[i]=(ans[i]+1ll*f[j]*h[j*2][i-j])%mod;
printf("%d\n",ans[i]);
pf[0]=1;
for(int j=1;j<=n;j++) pf[j]=1ll*ans[i]*pf[j-1]%mod;
for(int j=n*2;j;j--)
for(int k=1;k*i<=n&&k<=j;k++){
int coe=1ll*C[j][k]*pf[k]%mod;
for(int l=k*i;l<=n;l++)
h[j][l]=(h[j][l]+1ll*coe*h[j-k][l-i*k])%mod;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5772kb
input:
5 998244353
output:
2 10 70 588 5544 1 3 14 84 592
result:
wrong answer 1st numbers differ - expected: '1', found: '2'