QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#299168#7644. Good Splitsucup-team1525WA 1ms5772kbC++172.0kb2024-01-06 17:29:592024-01-06 17:30:01

Judging History

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

  • [2024-01-06 17:30:01]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5772kb
  • [2024-01-06 17:29:59]
  • 提交

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;
}

详细

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'