CF814E An unavoidable detour for home

一道比较神仙的dp

首先观察题目可知道由于每个点的dis相当于从1开始bfs的深度，并且dis单调不降，所以相当于建出bfs树后，每一层的节点的编号都是连续的

这就启发我们dp的状态设置为f[i][j]表示已经将前i个点加入到bfs树中了，并且最后一层有j个点的方案数

然后考虑怎么转移，发现我们只需要知道这一层有几个点和上一层分别有几个2、3点即可暴力转移与算答案

我们记g[i][j][k]表示下一层有i个点当前层有j个点2，k个点3它们之间连边的方案数

对其分类讨论一下，有如下四种情况

1、i=j=k=0

显然g[0][0][0]=1

2、i=j=0，k！=0

即只有度数为3的点，则去掉那些连向父亲的边后，每个点度数为2，它们一定形成了项链，直接用项链数与前面的状态暴算即可

3、i=0，j！=0，k！=0

则分别从可能变成度数为2的点和可能变成度数为3的点中取一个来和这个新加的点凑就行

4、i！=0，j！=0，k！=0

大体和3差不多

code

//quree
#include 
using namespace std;
#define rep(a,b,c) for(int a=(b);a<=(c);a++)
#define per(a,b,c) for(int a=(b);a>=(c);a--)
#define repe(x) for(int yny=head[x],v;yny&&(v=e[yny].v);yny=e[yny].u)
#define ll long long
#define pb emplace_back
template<class T>inline void read(T &x) {
    T f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
const int p=1e9+7;
const int inv2=((p+1)>>1);
int fac[51],inv[51];
inline int ksm(int a,int b) { int ans=1; for(;b;b>>=1,a=1ll*a*a%p) if(b&1) ans=1ll*a*ans%p; return ans; }
inline void init() {
    fac[0]=1; inv[0]=1;
    rep(i,1,50) fac[i]=1ll*i*fac[i-1]%p,inv[i]=ksm(fac[i],p-2);
}
inline int C(int a,int b) { return 1ll*fac[a]*inv[a-b]%p*inv[b]%p; }
int f[51][51],g[51][51][51],c2,c3,ans,n,d[51];
inline void solve() {
    init();
    rep(i,0,50) rep(j,0,50) rep(k,0,50) {
        if(!i&&!j&&!k) g[i][j][k]=1;
        else if(!i&&!j) {
            rep(l,2,k-1) (g[i][j][k]+=1ll*g[i][j][k-l-1]*C(k-1,l)%p*fac[l]%p*inv2%p)%=p;
        }
        else if(!i) {
            if(j>=2) (g[i][j][k]+=1ll*g[i][j-2][k]*(j-1)%p)%=p;
            if(k>=1) (g[i][j][k]+=1ll*g[i][j][k-1]*k%p)%=p;
        }
        else {
            if(j) (g[i][j][k]+=1ll*g[i-1][j-1][k]*j%p)%=p;
            if(k) (g[i][j][k]+=1ll*g[i-1][j+1][k-1]*k%p)%=p;
        }
    }
    read(n);
    rep(i,1,n) read(d[i]);
    f[d[1]+1][d[1]]=1;
    rep(i,d[1]+2,n) rep(j,1,i-d[1]-1) {
        c2=0; c3=0;
        rep(k,1,i-j) {
            if(d[i-j-k+1]==2) c2++;
            else c3++;
            (f[i][j]+=1ll*g[j][c2][c3]*f[i-j][k]%p)%=p;
        }
    }
    c2=0; c3=0;
    per(i,n,2) {
        if(d[i]==2) c2++;
        else c3++;
        (ans+=1ll*g[0][c2][c3]*f[n][n-i+1]%p)%=p;
    }
    printf("%d\n",ans);
}
int main() {
    //int TEST; read(TEST); while(TEST--)
    solve();
}

CF814E An unavoidable detour for home

相关

标签