我不会数数。

计数 DP 是一类 DP，强调不重不漏的一类 DP。

在设计状态上稍微有点毒瘤，且一般与组合数学有关。

Codeforces Round #313 Gerald and Giant Chess

  • http://codeforces.com/problemset/problem/559/C

先假设黑点的横纵坐标都是递增的，状态设计：fif_i 表示不经过任何在他前面的黑点到达该点的方案数，显然有：fi=Cxi+yi−2xi−1−∑j=1i−1fj×Cxi+yi−xj−yjxi−xj(xi≥xj,yi≥yj)f_i=C_{x_i+y_i-2}^{x_i-1}-\sum_{j=1}^{i-1} f_j\times C _{x_i+y_i-x_j-y_j}^{x_i-x_j}(x_i\ge x_j,y_i\ge y_j)。

直接转移即可，时间复杂度 O(n2)O(n^2)。

CEOI 2002 A Decorative Fence

  • http://poj.org/problem?id=1037

显然有一个试填法：设当前一位填 xx，统计符合条件的状态个数 TT，若 T≥ST\ge S，说明当前一位就是 xx，继续枚举下一位，否则 S=S−TS=S-T，x=x+1x=x+1 继续枚举。

考虑预处理出 TT 值来加速，设 fi,j,kf_{i,j,k} 表示共有 ii 块木板，最左边的木板高度为 jj，位置情况是 kk，有：

fi,j,0=∑p=ji−1fi−1,p,1fi,j,1=∑p=1j−1fi−1,p,0f_{i,j,0}=\sum^{i-1}_{p=j} f_{i-1,p,1}\\f_{i,j,1}=\sum^{j-1}_{p=1} f_{i-1,p,0}

暴力转移后试填即可，时间复杂度 O(n3)O(n^3)。

POJ 1737 Connected Graph

  • http://poj.org/problem?id=1737

设 fif_i 为含 ii 个点的有标号连通图个数，考虑 DP。

发现如果正着做比较难做，但显然，有 ii 个点的有标号无向图个数为 2i×(i−1)22^{\frac{i\times (i-1)}{2}} 个，考虑拿所有的减去不符合的，枚举 11 号点连通块所含的节点个数 jj。

有：

fi=2i×(i−1)2−∑j=1i−1fj×Ci−1j−1×2(i−j)×(i−j−1)2f_i=2^{\frac{i\times (i-1)}{2}}-\sum^{i-1}_{j=1} f_j\times C^{j-1}_{i-1} \times 2^{\frac{(i-j)\times (i-j-1)}{2}}

直接递推即可，时间复杂度 O(n2)O(n^2)，本题需要配合高精度，建议配合 Poly 后写 [集训队作业2013]城市规划。

How Many of Them?

  • https://www.luogu.com.cn/problem/P6596

本题较为复杂，供学有余力的读者思考。——《算法竞赛进阶指南》李煜东

设 fi,jf_{i,j} 为 ii 个点，含 jj 条割边的无向连通图数量，gi,j,kg_{i,j,k} 为 ii 个点，jj 个双连通分量，kk 条割边的无向连通图数量。

先处理 j>0j>0 的情况：

  • 枚举 11 号点所在双连通分量大小 kk，显然所在的双连通分量组成方案为 fk,0×Ci−1k−1f_{k,0}\times C_{i-1}^{k-1}。
  • 剩下的怎么求呢？联合 gi,j,kg_{i,j,k} 来求，又可以枚举一个 xx 表示删掉 11 号点所在双连通分量后的连通块个数，那就又有 gi−k,x,j−x×kxg_{i-k,x,j-x}\times k^x 种方案。

那么就有：

fi,j(j>0)=∑k=1i−1(fk,0×Ci−1k−1×∑x=1min⁡(i−k,j)gi−k,j,j−x×xkf_{i,j}(j>0)=\sum^{i-1}_{k=1}(f_{k,0}\times C_{i-1}^{k-1}\times \sum_{x=1}^{\min(i-k,j)} g_{i-k,j,j-x}\times x^k

设 hih_i 为含 ii 个点的连通图个数，容易发现 fi,0=hi=∑j=1i−1fi,jf_{i,0}=h_i=\sum^{i-1}_{j=1} f_{i,j}。

剩下的问题就是求 gi,j,kg_{i,j,k}：

  • 枚举含 11 号点的双连通分量，其大小为 pp，含割边为 qq，那么该双连通分量的组成方案也就有 fp,q×Ci−1p−1f_{p,q}\times C_{i-1}^{p-1} 个。
  • 其他部分的选法也就有 gi−p,j−1,k−qg_{i-p,j-1,k-q} 个。
  • 而要连接起来可以随便选一个点，所以又有 pp 个。

那么也就有：

gi,j,k=∑p=1i∑q=0kfp,q×Ci−1p−1×p×gi−p,j−1,k−qg_{i,j,k}=\sum^i_{p=1}\sum^k_{q=0} f_{p,q}\times C^{p-1}_{i-1}\times p\times g_{i-p,j-1,k-q}

综上所述，有：

hi=2i×(i−1)2−∑j=1i−1hj×Ci−1j−1×2(i−j)×(i−j−1)2fi,j(j>0)=∑k=1i−1(fk,0×Ci−1k−1×∑x=1min⁡(i−k,j)gi−k,j,j−x×xkfi,0=hi=∑j=1i−1fi,jgi,j,k=∑p=1i∑q=0kfp,q×Ci−1p−1×p×gi−p,j−1,k−qh_i=2^{\frac{i\times (i-1)}{2}}-\sum^{i-1}_{j=1} h_j\times C^{j-1}_{i-1} \times 2^{\frac{(i-j)\times (i-j-1)}{2}}\\f_{i,j}(j>0)=\sum^{i-1}_{k=1}(f_{k,0}\times C_{i-1}^{k-1}\times \sum_{x=1}^{\min(i-k,j)} g_{i-k,j,j-x}\times x^k\\f_{i,0}=h_i=\sum^{i-1}_{j=1} f_{i,j}\\g_{i,j,k}=\sum^i_{p=1}\sum^k_{q=0} f_{p,q}\times C^{p-1}_{i-1}\times p\times g_{i-p,j-1,k-q}

时间复杂度 O(n5)O(n^5)。