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$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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
唯一和上题不同在于可以向右下走。设 $d_{i,j}$ 为从 $(0,0)$ 走到 $(i,j)$ 的方案数。
枚举向右下走了几次，可以得到：
\[d_{i,j}=\sum_{k=0}^{\min(i,j)}\binom{i-k+j-k+k}{k}\binom{i-k+j-k}{i-k}\]第一个组合数表示剩下走 $i-k+j-k$ 中穿插着 $k$ 步，插板法，右边表示正常走。
发现模数很小，值域相对较大，组合数可以 Lucas 定理 $\mathcal O(\log_p n)$ 求。
然后就和上一道题一样了，状态和转移都是类似的。复杂度 $\mathcal O(k^2\min(n,m)\log_p n)$。
连通图
开始厉害了。
还是考虑容斥。$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$ 所在的连通块，已经强制保证它联通，所以只需考虑剩下的点和如何选点的问题。要开高精。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int n;
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$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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);
}