欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ4011: [HNOI2015]落忆枫音(dp 乘法原理)

程序员文章站 2022-04-14 20:17:43
题意 "题目链接" Sol 非常妙的一道题 设$inder[i]$表示$i$号节点的度数 首先如果是个DAG的话,可以考虑在每个点的入边中选一条边作为树形图上的边,这样$ans = \prod_{i 1} inder[i]$ 如果加入一条边的话,算答案的时候可能会把一些环的贡献也算进去(比如样例中$ ......

题意

题目链接

sol

非常妙的一道题

\(inder[i]\)表示\(i\)号节点的度数

首先如果是个dag的话,可以考虑在每个点的入边中选一条边作为树形图上的边,这样\(ans = \prod_{i > 1} inder[i]\)

如果加入一条边的话,算答案的时候可能会把一些环的贡献也算进去(比如样例中\(2 - 4 - 3\))这个环

考虑减去环上的贡献,注意形成的环不止一个,准确的来说,如果加入了\(x -> y\)这条边,那么在原图中所有\(y -> x\)的路径都应该计算贡献

其中一条路径的贡献为\(\frac{ans}{s \in (y -> x) inder[s]}\)

dp一遍求出所有贡献即可

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10, mod = 1e9 + 7;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, x, y, inder[maxn], inv[maxn], t[maxn], f[maxn];
vector<int> v[maxn];
void add(int &x, int y) {
    if(x + y < 0) x = x + y + mod;
    else x = (x + y >= mod ? x + y - mod : x + y);
}
int mul(int x, int y) {
    return 1ll * x * y % mod;
}
void topsort() {
    queue<int> q;
    for(int i = 1; i <= n; i++) if(!inder[i]) q.push(i); 
    while(!q.empty()) {
        int p = q.front(); q.pop(); f[p] = mul(f[p], inv[t[p]]); 
        for(int i = 0; i < v[p].size(); i++) {
            int to = v[p][i];
            add(f[to], f[p]); 
            if(!(--inder[to])) q.push(to);
        }
    }
}
int main() {
    n = read(); m = read(); x = read(); y = read();
    inv[1] = 1; for(int i = 2; i <= m + 1; i++) inv[i] = mul((mod - mod / i), inv[mod % i]); 
    for(int i = 1; i <= m; i++) {
        int x = read(), y = read();
        v[x].push_back(y); inder[y]++;
    }
    int ans = 1; inder[y]++; 
    for(int i = 2; i <= n; i++) ans = mul(ans, inder[i]); 
    if(y == 1) {cout << ans; return 0;}
    memcpy(t, inder, sizeof(inder));
    inder[y]--;
    f[y] = ans; topsort();
    cout << (ans - f[x] + mod) % mod;
    return 0;
}