\(\text{「CF848D」Shake It!}\)
\(\text{Solution}\)
我们可以发现题目中的图可以拆分为若干个递归的子结构，可以对这些子结构考虑 \(\text{DP}\)，设 \(f(i,j)\) 表示考虑对一个子结构 \((s,t)\) 加入 \(i\) 个点后形成的图最小割为 \(j\) 的本质不同方案数。推一下发现 \(f(i,j)\) 难以转移，发现子问题实质上在 \((s,t)\) 拓展若干次点 \(u\) 形成的结构 \((s,u)\) 和 \((u,t)\)，所以考虑设一个辅助状态 \(g(i,j)\) 表示对 \((s,t)\) 加入 \(i\) 个点后且保证只对 \((s,t)\) 拓展一次形成的图的最小割为 \(j\) 的本质不同方案数，先考虑转移 \(g(i,j)\)，容易发现
\[g(i,j)=\sum_{k}\sum_{min(x,y)=j}f(k,x)f(i-k-1,y) \]可以通过计算 \(f,g\) 的后缀和 \(F(i,j)=\sum_{k\ge j}f(i,k),G(i,j)=\sum_{k\ge j}g(i,k)\) 来降低复杂度
\[G(i,j)=\sum_{k}F(k,j)F(i-k-1,j) \]考虑转移 \(f(i,j)\)，发现 \(f(i,j)\) 便是在 \((s,t)\) 作用若干次 \(g(i_k,j_k)\) 的结果，满足 \(\sum i_k=i\) 且 \(\sum j_k=j-1\)，考虑 \(k\) 个 \(g(i,j)\) 的内部次序，由隔板法可知为 \(\binom{g(i,j)+k-1}{k}\)，用背包的方法合并即可，复杂度为 \(O(n^4\log n)\).
#include<bits/stdc++.h>
#define ll long long
#define PI pair<int,int>
#define PII pair< pair<int,int> , int >
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define MAXN (105)
#define MAXM (105)
#define MOD (1000000007)
using namespace std;
template<typename type>
void read(type &x)
{
x=0;char ch=0;bool ff=0;
while(ch<'0'||ch>'9'){ff|=!(ch^'-');ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x=ff?-x:x;
}
ll qpow(ll x,ll y)
{
ll res=1;
while(y)
{
if(y&1ll) res=res*x%MOD;
x=x*x%MOD,y>>=1ll;
}
return res;
}
int n,m;
ll fac[MAXN],ifac[MAXN],f[MAXN][MAXM],F[MAXN][MAXM],G[MAXN][MAXM];
void init()
{
fac[0]=1;
for(int i=1;i<=100;i++)
fac[i]=fac[i-1]*(ll)i%MOD;
ifac[100]=qpow(fac[100],MOD-2);
for(int i=99;i>=0;i--)
ifac[i]=ifac[i+1]*(ll)(i+1ll)%MOD;
}
int main()
{
init();
read(n),read(m);
f[0][0]=1,F[0][1]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i+1;j++)
for(int k=0;k<i;k++)
G[i][j]=(G[i][j]+F[k][j]*F[i-k-1][j]%MOD)%MOD;
for(int j=1;j<=i+1;j++)
{
ll gnow=((G[i][j]-G[i][j+1])%MOD+MOD)%MOD;
for(int a=n;a>=0;a--)
{
for(int b=n+1;b>=0;b--)
{
ll sum=0,dmul=1;
for(int k=0,sa=0,sb=0;sa<=a&&sb<=b;k++,sa+=i,sb+=j)
{
sum=(sum+dmul*ifac[k]%MOD*f[a-sa][b-sb]%MOD)%MOD;
dmul=dmul*(ll)(gnow+k)%MOD;
}
f[a][b]=sum;
}
}
}
for(int j=i+1;j;j--)
F[i][j]=(F[i][j+1]+f[i][j-1])%MOD;
}
printf("%lld",((F[n][m]-F[n][m+1])%MOD+MOD)%MOD);
}