1 条题解

  • 0
    @ 2026-7-4 12:02:07

    #include <cstdio>
    const int M = 305;
    #define int long long
    int read()
    {
    	int x=0,f=1;char c;
    	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
    	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    	return x*f;
    }
    int n,k,p,C[M][M],t[M][M],f[M][M];
    void add(int &x,int y) {x=(x+y)%p;}
    void init()
    {
    	for(int i=0;i<=n;i++)
    	{
    		C[i][0]=1;
    		for(int j=1;j<=i;j++)
    			C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
    	}
    	for(int i=1;i<=n;i++)
    		for(int k=1;k<=i;k++)
    			for(int j=1;j<=i;j++)
    				add(t[i][k],C[j-1][i-k]);
    }
    signed main()
    {
    	n=read();k=read();p=read();init();
    	f[0][0]=1;
    	for(int j=1;j<=k;j++)
    	{
    		f[0][j]=1;
    		for(int i=1;i<=n;i++)
    		{
    			for(int k=1;k<=i;k++)
    			{
    				int s=f[k-1][j-1]*f[i-k][j]%p;
    				add(f[i][j],s*t[i][k]%p);
    			}
    			add(f[i][j],f[i][j-1]);
    		}
    	}
    	printf("%lld\n",f[n][k]);
    }
    
    
    • 1

    信息

    ID
    8667
    时间
    2000ms
    内存
    1024MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者