计数DP

Copyright

本页面贡献者：CooolKey。 本页面内容遵循 MIT 协议，转载请附上原文出处链接和本声明。

要点：

学会将问题化为子问题

同时保证不重不漏

例题三

给定一个 n * m 的棋盘(1 ≤ n,m < 1e5)，棋盘上有 N (1 ≤ N ≤ 2000)个格子是黑色的，其他是白色的

初始位置在左上角，只能向下或向右移动，不能经过黑色格子

从左上角移动到右下角一用有多少种走法？

（输出时对 1e9+7 取模）

不考虑黑格子，从左上角移动到右下角的走法：C_{m+n}^m

可以注意到，棋盘很大，可是黑色格子数量很少

问题转换：

求从左上角移动到右下角会经过黑色格子的走法

子问题划分：

按照第一个经过的黑格子划分

解题思路：

假设终点也是黑色格子，排序后，设 dp[i] 为从起点走到第 i 个黑格子，且不经过其他黑格子的路线数

dp[i]=C_{x_i-1+y_i-1}^{x_i-1}-\sum_{j=0}^{i-1}dp[j]*C_{x_i-x_j+y_i-y_j}^{x_i-x_j}

快速幂板子

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
ll qpow(ll a,ll b)
{
    ll ans=1%mod;
    for(;b;b>>=1ll)
    {
        if(b&1ll)ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans;
}

组合数板子

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ll jc[200020],jcinv[200020];

ll inv(ll a)
{
    return qpow(a,mod-2);
}

void init(int n)
{
    jc[1]=1;jcinv[1]=inv(1);
    for(int i=2;i<=n;i++)
    {
        jc[i]=jc[i-1]*i%mod;
        jcinv[i]=inv(jc[i]);
    }
}

ll C(int n,int m)
{
    if(n==0) return 1;
    else if(n==m) return 1;
    return jc[m]*jcinv[n]%mod*jcinv[m-n]%mod;
}

例题四

求 N 个节点的无向连通图有多少个，节点有标号，编号为1～N（1 ≤ N ≤ 50）

显然，无向图的总数为2^{N(N-1)/2}

直接计算连通图很困难

问题转换：

求不连通图的个数

划分：

固定一个点，按照该点所在的连通图的节点个数划分

解题思路：

设 dp[i] 为 i 个节点的无向连通图的个数

dp[i]=2^{i(i-1)/2}-\sum^{i-1}_{j=1}dp[j]*C_{i-1}^{j-1}*2^{(i-j)(i-j-1)/2}

大数

可以在网上找大数板子

由于这个题只有50个数，也可以用python写完，把答案打印出来，用C语言直接输出

小建议

  • 遇到写不出来的题，看完题解后不仅仅要知道「为什么是这样写」，还要思考「为什么要这样想」
  • 对于ACM的技能加点，除了“计数DP，树上DP，组合数学，图论 ...”这种「专题类」的学习，像“拼凑思想，二分思想，转化为子问题，反向思考 ...”这样的「思想类」归纳也很重要