[NOI.AC#31]MST 计数类DP

链接

注意到 \(n\) 只有40，爆搜一下发现40的整数拆分（相当于把 \(n\) 分成几个联通块）很少

因此可以枚举联通块状态来转移，这个状态直接用vector存起来，再用map映射，反正40也不大

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i(a);i<=(b);++i)
using namespace std;
typedef long long ll;
const int N=4e4+5;
vector<int>s,sta[N];
map<vector<int>,int>mp;
#define pb push_back
int n,sum,cnt,val[N],f[45][N],fac[2003],inv[2003],a[45],tmp[45];
void dfs(int x,int m){
    if(!x){sta[++cnt]=s,val[mp[s]=cnt]=sum;return;}
    for(int i=min(x,m);i;--i)
    s.pb(i),sum+=i*(i-1)/2,dfs(x-i,i),sum-=i*(i-1)/2,s.pop_back();
}
const int p=1e9+7;
inline void inc(int&x,int y){x+=y,x>=p&&(x-=p);}
inline int fpow(int x,int k){int r=1;for(;k;k>>=1,x=1ll*x*x%p)if(k&1)r=1ll*r*x%p;return r;}
inline int calc(int n,int m){return n<m?0:1ll*fac[n]*inv[n-m]%p;}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n;dfs(n,n);fac[0]=inv[0]=1;
    REP(i,1,n*n)fac[i]=1ll*fac[i-1]*i%p;inv[n*n]=fpow(fac[n*n],p-2);
    for(int i=n*n-1;i;--i)inv[i]=1ll*inv[i+1]*(i+1)%p;
    REP(i,1,n-1)cin>>a[i];s.clear();
    REP(i,1,n)s.pb(1);f[0][mp[s]]=1;
    REP(i,0,n-2)REP(k,1,cnt){
        int u=1ll*f[i][k]*calc(val[k]-a[i],a[i+1]-a[i]-1)%p;
        if(!u)continue;int c=0;
        for(int x:sta[k])tmp[++c]=x;
        REP(p1,1,c)REP(p2,p1+1,c){
            s.clear();int t=tmp[p1]+tmp[p2];
            REP(p,1,c)if(p^p1&&p^p2){
                if(t>=tmp[p])s.pb(t),t=-1;s.pb(tmp[p]);
            }if(~t)s.pb(t);
            inc(f[i+1][mp[s]],1ll*u*tmp[p1]*tmp[p2]%p);
        }
    }
    cout<<1ll*f[n-1][1]*fac[n*(n-1)/2-a[n-1]]%p;
    return 0;
}

[NOI.AC#31]MST 计数类DP

原文：https://www.cnblogs.com/HolyK/p/9838187.html