题解 CF848D 【Shake It!】
猪脑子
·
·
题解
又是一个好题
首先，设f_{n,m}为进行n次操作，能够得到的最小割为m的本质不同的图的个数，这也是我们想要求的答案。
那么如何求这个东西呢？我们首先看一下这个最小割。容易知道最小割就等于最大流，后面我们就用流来考虑，因为这样说起来容易一些。
不难发现，题目中构造出来的图的最大流会由两部分组成：源点和汇点之间产生1的流量；从源点开始，经过旁边的若干点，再流到汇点。
我们重点看一下后一种情况，我们考虑每一个从(S,T)这条边延伸出来的点（比如下面的点A），源点到它的最大流是x，它到汇点的最大流是y，那么它就可以产生\min(x,y)的流量。
而对于(S,A)和(A,T)这两部分，我们发现它是一个跟(S,T)一模一样的子问题。
为了算f_{n,m}，我们设g_{n,m}代表考虑一条像S\to A\to T这样的路径，这条路径上的最大流是m，并且一共进行了n次操作（这里包含了从(S,T)扩展出A的那一次操作），h_{n,m}类似，表示的是最大流不少于m的方案数，同时也设F_{n,m}代表f_{n,m}的后缀和（意思也是最大流不少于m），那么有下面的式子：
h_{n,m}=\sum_{i=0}^{n-1}F_{i,m}\times F_{n-i-1,m},g_{n,m}=h_{n,m}-h_{n,m+1}
现在,我们希望用$g_{n,m}$来算$f_{n,m}$，但是由于从一条边可能会同时扩展出多个节点，所以这一部分做法并不是那么显然。
我们设$dp_{n,m}$表示选出若干个$g_{a,b}$，使得一共消耗$n$次操作步数，且产生的最大流的和为$m$，这样的方案数（意思就是从$S\to T$这条边扩展出若干个点，然后再为这若干个点对应的路径安排一定的步数和流量，算一下这种情况的方案数）。但是如果我们单纯枚举$a,b$去计算这种东西的话，我们会算重，因为两个同构的图我们可能算了好几遍。
首先由一个思路是给$g_{a,b}$钦定一个顺序：按照$a$从小到大，$b$从小到大的顺序一个个加入$g_{a,b}$，然后剩下的就类似于一个背包。这样的话，对于$(a,b)$不同的那些路径，我们确实可以不重复计算方案。但是对于$(a,b)$相同的情况，如果还是简单地将$g_{a,b}$一个个乘进去，那还是会算重。
这怎么办呢？考虑一个$(a,b)$，我们假设$g_{a,b}=x$，那么如果我们选择$c$个这样的路径，方案数应该是多少呢？由于路径之间没有顺序，我们不妨给这些路径编号为$1\dots x$，然后要求按照从小到大的顺序选择。那么不难发现方案数就是$C_{x+c-1}^c$（考虑往$x-1$个点中间或两边插入一共$c$个板子，每种方法就对应了一个选数的方案）。
因此我们在用$g_{a,b}$转移时，我们就可以枚举$g_{a,b}$的个数$c$，然后将一个组合数加进答案（由于$c$很小，所以组合数直接算就可以了）。
具体怎么dp可以参考我的代码。（代码中$dp$是实时计算的，因为算$f_{n,m}$用到的$g_{a,b}$中的$a$不会超过$n$，所以不会出错）。
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int Mod=1000000007;
int f[61][61];
int F[61][61];
int g[61][61];
int h[61][61];
int dp[61][61];
int fac[61],inv[61];
int fpow(int a,int b)
{
int ans=1,t=a;
while(b)
{
if(b&1)ans=1ll*ans*t%Mod;
t=1ll*t*t%Mod;b>>=1;
}
return ans;
}
void init()
{
int N=55;
fac[0]=inv[0]=1;
for(int i=1;i<=N;i++)
{
fac[i]=1ll*fac[i-1]*i%Mod;
inv[i]=fpow(fac[i],Mod-2);
}
return ;
}
int calc(int n,int m,int a,int b)
{
int ans=0;
int cur=1;
for(int i=0;i*a<=n&&i*b<=m;i++)
{
ans=(ans+1ll*dp[n-i*a][m-i*b]*cur%Mod*inv[i])%Mod;
cur=1ll*cur*(g[a][b]+i)%Mod;
}
return ans;
}
int main()
{
init();
int n,m;
scanf("%d %d",&n,&m);
f[0][1]=1;dp[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=n+1;j>=1;j--)
F[i-1][j]=(F[i-1][j+1]+f[i-1][j])%Mod;
for(int j=n+1;j>=1;j--)
{
h[i][j]=0;
for(int k=0;k<i;k++)
h[i][j]=(h[i][j]+1ll*F[k][j]*F[i-k-1][j])%Mod;
g[i][j]=(h[i][j]-h[i][j+1]+Mod)%Mod;
}
for(int j=1;j<=n+1;j++)
{
for(int x=n;x>=0;x--)
for(int y=n+1;y>=0;y--)
dp[x][y]=calc(x,y,i,j);
}
for(int j=1;j<=n+1;j++)
f[i][j]=dp[i][j-1];
}
printf("%d\n",f[n][m]);
return 0;
}
```
~~所以这题还是挺好玩的对吗~~