My Blogs
开个新坑，目前大多数是蓝书上的题。
不会更高级的东西，只写怎么数数，不考虑高级优化。
状态设计：这里满足的要求不再是无后效性，而是要求一个阶段的所有状态能不重不漏的覆盖掉所有情况。
转移：寻找合适的基准点，围绕这个基准点把大的状态拆出一个小的不可划分的状态，和剩下的状态进行计算（一般是乘起来）。
过河卒plus
基础题。黑色格子很少，但是棋盘大小非常大，做法应当和值域无关，而是和黑格子的数量相关。先把黑色格子按横坐标为第一关键字，纵坐标为第二关键字排序。
引理：从 \((0,0)\) 只向下和向右走到 \((n,m)\) 的方案数为 \(\binom{n+m}{n}\)。
证明：一定向下走 \(n\) 步，向右走 \(m\) 步，总步数 \(n+m\)。看成一个 \(n+m\) 的数列，把其中 \(n\) 个染成黑色，其余白色，表示黑色的操作是向下走，所以答案即为 \(\binom{n+m}{n}\)。
直接算不经过所有黑格子的路径数是不好算的。正难则反，考虑用容斥的思想，设计 \(f_i\) 表示只经过第 \(i\) 个黑色格子并且停留在第 \(i\) 个黑色格子的方案数。
转移方程为 \(f_i=\binom{x_i+y_i}{x_i}-\sum_{j=1}^{n}[x_j\leq x_i\wedge y_j\leq y_i]\binom{x_i-x_j+y_i-y_j}{x_i-x_j}f_j\)。
如果没有任何限制，则 \(f_i=\binom{x_i+y_i}{x_i}\)。划分基准点：即枚举第一个经过的黑色格子 \(j\) 为基准点。基准点前面只经过了白色格子，是不可划分的小状态。基准点后面到 \(i\) 的路径是随便走的，是大的状态减去不可划分的状态剩下的剩余状态，这部分没有限制，可以随便走，因为我们的不可划分状态是经过格子 \(j\) 前面的路径，这样才能做到不重不漏。
最后 \(ans=\binom{A+B}{A}-\sum_{j=1}^n\binom{A+B-x_j-y_j}{A-x_j}f_j\)。
void exgcd(int a,int b,int &x,int &y)
{
if(!b)return x=1,y=0,void();
exgcd(b,a%b,x,y);int z=x;x=y,y=z-x*(a/b);
}
int f[2002],x,y,g[200001],inv[200001];
pii a[2002];
inline int C(int n,int m){return g[n]*inv[m]%MOD*inv[n-m]%MOD;}
int n;
inline void mian()
{
g[0]=inv[0]=1;
for(int i=1;i<=200000;++i)g[i]=g[i-1]*i%MOD,exgcd(g[i],MOD,inv[i],y),inv[i]=(inv[i]%MOD+MOD)%MOD;
read(x,y,n),g[0]=1,a[0].fi=a[0].se=1,a[n+1].fi=x,a[n+1].se=y;
for(int i=1;i<=n;++i)read(a[i].fi,a[i].se);
sort(a+1,a+1+n);
for(int i=1;i<=n+1;++i)
{
f[i]=C(a[i].fi+a[i].se-2,a[i].fi-1);
for(int j=0;j<i;++j)
{
if(a[j].fi<=a[i].fi&&a[j].se<=a[i].se)
f[i]=(f[i]-f[j]*C(a[i].fi-a[j].fi+a[i].se-a[j].se,a[i].fi-a[j].fi)%MOD+MOD)%MOD;
}
}
write(f[n+1]);
}
过河卒plusplus 咕咕咕，做完再写。
连通图
开始厉害了。
还是考虑容斥。\(n\) 个点的连通图共有 \(\dfrac{n(n-1)}{2}\) 条边，总方案数是 \(2^{\frac{n(n-1)}{2}}\)，考虑如何计算不合法的方案数。
选取基准点，枚举 \(i\) 所在的连通块的大小 \(j\)，要从剩下的 \(i-1\) 个点中选 \(j-1\) 个（因为 \(1\) 号点必选），剩余的点间随意连边，得到转移方程：
\(f_i=2^{\frac{n(n-1)}{2}}-\sum_{j=1}^{i-1}\binom{i-1}{j-1}2^{\frac{(i-j)(i-j-1)}{2}}f_j\)。
这里不可划分的状态即为 \(i\) 所在的连通块，已经强制保证它联通，所以只需考虑剩下的点和如何选点的问题。要开高精。
int n;
struct Node{int len,a[5001];}C[51][51],f[51];
Node operator *(const Node nd1,const Node nd2)
{
Node nd3;nd3.len=nd1.len+nd2.len-1,memset(nd3.a,0,sizeof(nd3.a));
for(int i=1;i<=nd1.len;++i)
{
for(int j=1;j<=nd2.len;++j)
nd3.a[i+j-1]+=nd1.a[i]*nd2.a[j];
}
for(int i=1;i<=nd3.len;++i)nd3.a[i+1]+=nd3.a[i]/10,nd3.a[i]%=10;
while(nd3.a[nd3.len+1])++nd3.len,nd3.a[nd3.len+1]+=nd3.a[nd3.len]/10,nd3.a[nd3.len]%=10;
return nd3;
}
Node operator *(const Node nd1,const int x)
{
Node nd3;nd3.len=nd1.len,memset(nd3.a,0,sizeof(nd3.a));
for(int i=1;i<=nd3.len;++i)nd3.a[i]=nd1.a[i]*x,nd3.a[i+1]+=nd3.a[i]/10,nd3.a[i]%=10;
while(nd3.a[nd3.len+1])++nd3.len,nd3.a[nd3.len+1]+=nd3.a[nd3.len]/10,nd3.a[nd3.len]%=10;
return nd3;
}
Node power(Node nd1,int x)
{
Node ans;ans.len=1,ans.a[1]=1;
for(;x;nd1=nd1*nd1,x>>=1)if(x&1)ans=ans*nd1;
return ans;
}
Node operator -(const Node nd1,const Node nd2)
{
Node nd3;nd3.len=nd1.len,memset(nd3.a,0,sizeof(nd3.a));
for(int i=1;i<=nd1.len;++i)
{
nd3.a[i]+=nd1.a[i]-nd2.a[i];
if(nd3.a[i]<0)nd3.a[i]+=10,--nd3.a[i+1];
}
while(!nd3.a[nd3.len])--nd3.len;
return nd3;
}
Node operator +(const Node nd1,const Node nd2)
{
Node nd3;memset(nd3.a,0,sizeof(nd3.a)),nd3.len=max(nd1.len,nd2.len);
for(int i=1;i<=max(nd1.len,nd2.len);++i)nd3.a[i]+=nd1.a[i]+nd2.a[i],nd3.a[i+1]+=nd3.a[i]/10,nd3.a[i]%=10;
while(nd3.a[nd3.len+1])++nd3.len,nd3.a[nd3.len+1]+=nd3.a[nd3.len]/10,nd3.a[nd3.len]%=10;
return nd3;
}
inline void print(Node nd){for(int i=nd.len;i>=1;--i)cout<<nd.a[i];puts("");}
inline void mian()
{
C[1][1].len=1,C[1][1].a[1]=1;
for(int i=2;i<=50;++i)for(int j=1;j<=i;++j)C[i][j]=C[i-1][j]+C[i-1][j-1];
Node nd1;memset(nd1.a,0,sizeof(nd1.a)),nd1.a[nd1.len=1]=2;
for(int i=1;i<=50;++i)
{
f[i]=power(nd1,(i*(i-1))>>1);
for(int j=1;j<i;++j)
f[i]=f[i]-(f[j]*C[i][j]*power(nd1,((i-j)*(i-j-1))>>1));
}
while(1)
{
read(n);
if(!n)return;
print(f[n]);
}
}
连通图plus
第一眼设计 \(f_{i,j}\) 表示 \(i\) 个点，\(j\) 条割边的方案数，还是类似上面的方式容斥，总方案数上一个题已经求出，然后减去不合法的状态。然后就不会了。
问题在于无法准确的划分不可分割的子问题。如果还是像上一道题枚举 \(1\) 所在边双的大小（设为 \(h_i\)），但这时删去 \(1\) 号点所在边双后可能会分成许许多多的连通块，暴力枚举大小是指数级的，复杂度原地升天。
既然问题在于会出现多个连通块，就考虑加一维状态记录连通块的数量，\(g_{i,j,k}\) 表示 \(i\) 个点，\(j\) 个连通块，\(k\) 条割边的方案数。
注意 \(g\) 不能代替 \(f\)。这里可能会觉得 \(g_{i,1,j}=f_{i,j}\)，但是其实不是，下文会讲。
\(g\) 的基准点：首先枚举编号最小的点所在连通块的大小，然后枚举编号最小的点所在联通块内割边的数量：转移方程：
\[g_{i,j,k}=\sum_{p=1}^{i}\sum_{q=0}^{k}f_{p,q}\binom{i-1}{p-1}g_{i-p,j-1,k-q}p \]\(p\) 枚举连通块大小，\(q\) 枚举割边数量。组合数是选取连通块的点，\(f_{p,q}\) 是该连通块的方案数，\(g_{i-p,j-1,k-q}\) 是剩余的方案数。你会发现最后多了一个 \(p\)，但是正常推式子推不出来。
这里感觉蓝书讲的不是特别清楚，着重写一下。此处其实是一个类似于费用提前计算的思想，因为从 \(g\) 转移到 \(f\) 的时候对于每个连通块，会乘它的连通块的点数量，表示 \(1\) 号点连向了哪个点。所以 \(g_{i,j,k}\) 的真实含义是：\(i\) 个点，\(j\) 个连通块，\(k\) 条割边，对后面答案计算的总贡献。这样我们得到了完整的转移方程：
\[\begin{align*} h_i&=2^{\frac{i*(i-1)}{2}}-\sum_{j=1}^{i-1}\binom{i-1}{j-1}2^{\frac{(i-j)*(i-j-1)}{2}}h_j\\ f_{i,j}&=\sum_{k=1}^{i-1}f_{k,0}\binom{i-1}{k-1}\sum_{t=1}^{\min(i-k,j)}k^{t}g_{i-k,t,j-t}\\ f_{i,0}&=h_i-\sum_{j=1}^{i-1}f_{i,j}\\ g_{i,j,k}&=\sum_{p=1}^{i}\sum_{q=0}^{k}f_{p,q}p\binom{i-1}{p-1}g_{i-p,j-1,k-q} \end{align*} \]第二行的 \(k\) 是枚举 \(1\) 所在边双的点数，\(t\) 枚举移除 \(1\) 所在边双后有几个连通块，意义还是很明显的。其中删除后每个连通块的点连向 \(1\) 的边的系数上文中已经计算。
初值 \(f_{0,0}=g_{0,0,0}=1\)。
int n,m,fr[51],inv[51],f[51][51],g[51][51][51],h[51];
inline int power(int x,int y){int s=1;for(;y;y>>=1,Mmul(x,x))if(y&1)Mmul(s,x);return s;}
inline int C(int n,int m){return n<m||m<0?0:Cmul(fr[n],inv[m],inv[n-m]);}
inline void mian()
{
fr[0]=inv[0]=h[0]=1;
for(int i=1;i<=50;++i)fr[i]=Cmul(fr[i-1],i);
inv[50]=power(fr[50],MOD-2);
for(int i=49;i>=1;--i)inv[i]=Cmul(inv[i+1],i+1);
for(int i=1;i<=50;++i)
{
h[i]=power(2,i*(i-1)/2);
for(int j=1;j<i;++j)Mdel(h[i],Cmul(h[j],C(i-1,j-1),power(2,(i-j)*(i-j-1)/2)));
}
g[0][0][0]=f[0][0]=1;
// for(int i=0;i<=50;++i)for(int j=0;j<=50;++j)g[0][i][j]=1;
for(int i=1;i<=50;++i)
{
f[i][0]=h[i];
for(int j=1;j<i;++j)
{
for(int k=1;k<i;++k)
{
for(int t=1;t<=min(i-k,j);++t)
Madd(f[i][j],Cmul(f[k][0],C(i-1,k-1),power(k,t),g[i-k][t][j-t]));
}
Mdel(f[i][0],f[i][j]);
}
for(int j=1;j<=i;++j)
{
for(int k=0;k+j<=i;++k)
{
for(int p=1;p<=i;++p)
{
for(int q=0;q<=k;++q)
Madd(g[i][j][k],Cmul(f[p][q],p,C(i-1,p-1),g[i-p][j-1][k-q]));
}
}
}
}
read(n,m);int ans=0;
for(int j=0;j<=min(n-1,m);++j)Madd(ans,f[n][j]);
write(ans);
}