计数DP总结

P3244 [HNOI2015] 落忆枫音

记每个节点的入度为\(in_i\)
易得对于一个DAG,其生成树数量为\(\prod_{i=1}^{n} in_i\)
但加了新边之后，这张图可能会存在环，会出现一些方案是不合法的。我们便要容斥一下，把不合法的方案去掉。
那我们就考虑不合法方案数怎么算。
记新加的边为\(s->t\)
那么环的数量就等同于原图中\(t->s\)路径的数量
那么我们再去考虑每一个环
我们可以给环上每个节点钦定一个父亲
那么环上每个节点对于答案的贡献就从\(in_i\)变为了\(1\)
记环上的节点为\(w\)
那么这个环对于不合法方案数的贡献即为\(\frac{\prod_{i=1}^{n} in_i}{\prod in_w}\)
注意到这个东西可以dp一下
设\(f_i\)为从\(i\)到\(s\)的路径中上面这个式子的值。
初始化\(f_s\)为原图中\(\prod_{i=1}^{n} in_i  \div in_s\)
转移方程：\(f_u = \frac{\sum_{v}^{} f_v}{in_u}(u->v)\)、
最终的答案即为\(f_t\)
那我们便可以反向建图，在反图中记忆化搜索，在回溯时进行转移。
注意，因为转移方程中有除法，所以要求逆元。
Code:

[code]#includeusing namespace std;#define ll long longconst int N = 1e5 + 7, M = 2e5 + 7, p = 1e9 + 7;int n, m, from, to;ll dp[N];ll ans, du[N], f[N], s;bool vis[N];ll fpow(ll x, ll y){        ll sum = 1;        while(y){                if(y & 1) sum = sum * x % p;                x = x * x % p;                y >>= 1;        }        return sum;}struct Edge{        int head[N], tot;        struct edge{                int to, pre;        }e[M];        void add(int x, int y){                e[++tot] = {y, head[x]};                   head[x] = tot;                du[x]++;        }        void dfs(int u){                if(vis || u == to) return;                vis = 1;                for(int i = head; i; i = e.pre){                        int v = e.to;                        dfs(v);                        f = (f + f[v] * fpow(du, p - 2) % p) % p;                }        }}E;int main(){        scanf("%d%d%d%d", &n, &m, &from, &to);        for(int i = 1, x, y; i = 1;        }        return sum;}int main(){        scanf("%d%d", &n, &m);        a[0] = f[0] = 1;        ll t = fpow(2, n) - 1, r = 1;        for(int i = 1; i = 1;        }        return sum;}void init(){        f[1] = fac[0] = fac[1] = 1;        for(int i = 2; i > 1] + 1;                fac = fac[i - 1] * i % p;        }        int m = min(p - 1, n);        inv[m] = fpow(fac[m], p - 2);        for(int i = m - 1; i >= 0; i--){                inv = inv[i + 1] * (i + 1) % p;        }}ll C(ll x, ll k){        return fac[x] * inv[k] % p * inv[x - k] % p;}ll lucas(ll x, ll k){        return k == 0 ? 1 : (C(x % p, k % p) * lucas(x / p, k / p) % p);}int main(){        scanf("%d%d", &n, &p);        init();        f[1] = f[2] = 1;        f[3] = 2;        int l = 1, r = 1;        for(int i = 4; i

谢谢楼主提供！