[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

最新文章

热门文章