计数DP总结
P3244 落忆枫音记每个节点的入度为\(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:
#includeusing namespace std;#define ll long longconst int N = 1e5 + 7, M = 2e5 + 7, p = 1e9 + 7;int n, m, from, to;ll dp;ll ans, du, f, s;bool vis;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, tot; struct edge{ int to, pre; }e; void add(int x, int y){ e[++tot] = {y, head}; head = tot; du++; } 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 * 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 = f = 1; ll t = fpow(2, n) - 1, r = 1; for(int i = 1; i = 1; } return sum;}void init(){ f = fac = fac = 1; for(int i = 2; i > 1] + 1; fac = fac * i % p; } int m = min(p - 1, n); inv = fpow(fac, p - 2); for(int i = m - 1; i >= 0; i--){ inv = inv * (i + 1) % p; }}ll C(ll x, ll k){ return fac * inv % p * inv % 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 = f = 1; f = 2; int l = 1, r = 1; for(int i = 4; i 谢谢楼主提供！ 过来提前占个楼 感谢，下载保存了 谢谢楼主提供！ 鼓励转贴优秀软件安全工具和文档！ 分享、互助 让互联网精神温暖你我 收藏一下 不知道什么时候能用到 用心讨论，共获提升！ yyds。多谢分享 热心回复！ 感谢分享，下载保存了，貌似很强大 热心回复！ 前排留名，哈哈哈
页:
[1]