CF1439D INOI Final Contests

· · 题解

设 f(i,j) 为 i 台位置， j 个人的总答案。

如何转移？发现若 i>j 总有位置空着，枚举最右边非空的一段长度 k ，若 k=0 就是 f(i-1,j) 。

发现写出转移时还需要用到方案数，于是设 g(i,j) 为 i 台位置， j 个人的合法方案数。

于是，对于 i>j ，分类讨论一下两个贡献，乘上组合数：

f(i,j)=f(i-1,j)+\sum_{k>0} (f(i-k-1,j-k)g(k,k)+f(k,k)g(i-k-1,j-k))\times C_j^k

对于 g 也枚举右边一段或最右边为空。

g(i,j)=g(i-1,j)+\sum_{k>0}(g(k,k)g(i-k-1,j-k))\times C_j^k

那么对于 i=j 还要特殊计算。

如何转化为子问题？

可以枚举最后一个人坐下的位置，设为 j 。

方案数：最后一个人可以是这个位置的两个方向，其余位置的一个方向，(i+1) 种。其余 i-1 个人选 j-1 个坐左边，要乘上组合数。

g(i,i)=(i+1) \times \sum_{j=1}^{i} g(j-1,j-1)g(i-j,i-j)C_{i-1}^{j-1}

答案：设 Sum(i)=\sum_{j=1}^i j ，最后一个人的贡献为 (Sum(j-1)+Sum(i-j))(g(j-1,j-1)g(i-j,i-j)C_{i-1}^{j-1})

其他贡献: (i+1)C_{i-1}^{j-1}(f(j-1,j-1)g(i-j,i-j)+f(i-j,i-j)g(j-1,j-1))

昨天口胡了一下，今天来补代码：

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
typedef pair<int,int>pii;

int mod;
struct modint{
    int x;
    modint(int o=0){x=o;}
    modint &operator = (int o){return x=o,*this;}
    modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
    modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
    modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
    modint &operator ^=(int b){
        modint a=*this,c=1;
        for(;b;b>>=1,a*=a)if(b&1)c*=a;
        return x=c.x,*this;
    }
    modint &operator /=(modint o){return *this *=o^=mod-2;}
    modint &operator +=(int o){return x=x+o>=mod?x+o-mod:x+o,*this;}
    modint &operator -=(int o){return x=x-o<0?x-o+mod:x-o,*this;}
    modint &operator *=(int o){return x=1ll*x*o%mod,*this;}
    modint &operator /=(int o){return *this *= ((modint(o))^=mod-2);}
    template<class I>friend modint operator +(modint a,I b){return a+=b;}
    template<class I>friend modint operator -(modint a,I b){return a-=b;}
    template<class I>friend modint operator *(modint a,I b){return a*=b;}
    template<class I>friend modint operator /(modint a,I b){return a/=b;}
    friend modint operator ^(modint a,int b){return a^=b;}
    friend bool operator ==(modint a,int b){return a.x==b;}
    friend bool operator !=(modint a,int b){return a.x!=b;}
    bool operator ! () {return !x;}
    modint operator - () {return x?mod-x:0;}
};
#define maxn 505
int n,m;
modint fac[maxn],ifac[maxn];
modint f[maxn][maxn],g[maxn][maxn];
bool vf[maxn][maxn],vg[maxn][maxn];
inline void prework(int n){
    fac[0]=1;
    For(i,1,n)fac[i]=fac[i-1]*i;
    ifac[n]=1/fac[n];
    Rep(i,n-1,0)ifac[i]=ifac[i+1]*(i+1);
}
inline modint C(int n,int m){return fac[n]*ifac[m]*ifac[n-m];}

modint F(int i,int j);
modint G(int i,int j);
inline modint sum(int x){return 1ll*x*(x+1)/2%mod;}
modint F(int i,int j)
{
    if(vf[i][j])return f[i][j];
    vf[i][j]=1,f[i][j]=0;
    if(i==j){
        For(k,1,i)
            f[i][i]+=C(i-1,k-1)*(i+1)*(G(k-1,k-1)*F(i-k,i-k)+G(i-k,i-k)*F(k-1,k-1)),
            f[i][i]+=C(i-1,k-1)*G(k-1,k-1)*G(i-k,i-k)*(sum(k-1)+sum(i-k));
        return f[i][i];
    }
    f[i][j]=F(i-1,j);
    For(k,1,j)
        f[i][j]+=C(j,k)*(F(i-k-1,j-k)*G(k,k)+F(k,k)*G(i-k-1,j-k));
    return f[i][j];
}
modint G(int i,int j)
{
    if(vg[i][j])return g[i][j];
    vg[i][j]=1,g[i][j]=0;
    if(i==j){
        if(!i)return g[i][i]=1;
        For(k,1,i)
            g[i][i]+=G(k-1,k-1)*G(i-k,i-k)*C(i-1,k-1); 
        g[i][i]*=(i+1);
        return g[i][i];
    }
    g[i][j]=G(i-1,j);
    For(k,1,j)
        g[i][j]+=G(i-k-1,j-k)*G(k,k)*C(j,k);
    return g[i][j];
}

signed main()
{
    n=read(),m=read(),mod=read(),prework(501);
    cout<<F(n,m).x<<endl;
    return 0;
}