P17397 [ICPC 2018 Shenyang R] Counting Sheep in Ami Dongsuo 题解

tooolazy · 2026-10-22 15:30:11 · 题解

非常老题啊。

我们考虑先固定一个起点 u，然后通过拓扑排序算出到达每个点的路径数量 {\rm count}(u,v)。

为了处理这个题意需要的背包状物，我们写出生成函数：

其中 a(v) 就是 v 的点权。由于三元路径集合内部无序不重，最终的答案多项式可以通过容斥写出：

不难发现，对于每个 u，我们是可以 O(n+m) 地得出 f_u 的各项系数的，但是算 g 的时候我们必须 O(w^2) 地做多项式乘法，这无疑令我们感到不快。

（任意模数 ntt？算了吧 bro

一个很牛的技巧是，我们发现 f_u 实际上是可以递推的：

那我们不妨直接改记多项式的 3w+1 个点值呢？

是啊，点值可以直接参与运算，于是我们在拓扑排序复杂度不变的情况下，直接砍掉了多项式乘法的部分。

只需要把 g 的各点值算出，最后拉插即可，复杂度 O(mw+w^2)，记得把 f_u(z),f_u(z^2),f_u(z^3) 的点值都记一下。

代码是我一百万年前写的可能比较甜。

#include <iostream>
#include <cstring>
#include <vector>
#include <bitset>
using namespace std;

const int MAXN = 1e4 + 5, MAXW = 405, MAXDOT = MAXW * 3;
constexpr int MOD = 1e9 + 7;
int n, m, w, value[MAXN];
int f[3][MAXN][MAXDOT];
int g[MAXN][MAXDOT], h[MAXDOT];
vector<int> graph[MAXN];
bitset<MAXN> vis;
void input() {
    cin >> n >> m >> w;
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    memset(h, 0, sizeof(h));
    for (int i = 1; i <= n; i ++)
        graph[i].clear(), vis[i] = false, cin >> value[i];
    while (m --) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }
}

typedef long long LL;
inline int fastpow(int x, int p) {
    int res = 1;
    for (; p; p >>= 1, x = (LL)x * x % MOD)
        if (p & 1) res = (LL)res * x % MOD;
    return res;
}
inline int inv(int x) {
    if (x < 0) return MOD - fastpow(-x, MOD - 2);
    return fastpow(x, MOD - 2);
}

void solve(int u) {
    static int INV6 = fastpow(6, MOD - 2);
    if (vis[u]) return;
    vis[u] = true;
    for (int v : graph[u]) {
        solve(v);
        for (int t = 0; t < 3; t ++)
            for (int i = 0; i <= 3 * w; i ++)
                (f[t][u][i] += f[t][v][i]) %= MOD;
    }
    for (int x = 0; x <= 3 * w; x ++) {
        int pow = fastpow(x, value[u]);
        for (int t = 0; t < 3; t ++)
            (f[t][u][x] += fastpow(pow, t + 1)) %= MOD;
        LL bxlzk = (LL)fastpow(f[0][u][x], 3)
                 - (3LL * f[0][u][x] * f[1][u][x]) % MOD
                 + 2LL * f[2][u][x];
        g[u][x] = (MOD + bxlzk % MOD) % MOD;
        g[u][x] = (LL)g[u][x] * INV6 % MOD;
        (h[x] += g[u][x]) %= MOD;
    }
}

void multiply(vector<int> & p, int xi) {
    int deg = p.size();
    p.push_back(p.back());
    for (int i = deg - 1; i; i --) {
        p[i] = p[i - 1] - (LL)p[i] * xi % MOD;
        p[i] = (MOD + p[i]) % MOD;
    }
    p[0] = (MOD - (LL)p[0] * xi % MOD) % MOD;
}
void divide(vector<int> & p, int xi) {
    int least = p.back();
    p.pop_back();
    int deg = p.size() - 1;
    for (int i = deg; i >= 0; i --) {
        int sub = (LL)least * xi % MOD;
        swap(p[i], least);
        least = (least + sub) % MOD;
    }
}

int b[MAXDOT];
vector<int> pf;
void Lagrange() {
    memset(b, 0, sizeof(b));
    pf.clear();
    pf.push_back(1);
    for (int i = 0; i <= 3 * w; i ++)
        multiply(pf, i);
    for (int i = 0; i <= 3 * w; i ++) {
        int d = h[i];
        for (int j = 0; j <= 3 * w; j ++) {
            if (i == j) continue;
            d = (LL)d * inv(i - j) % MOD;
        }
        divide(pf, i);
        for (int j = 0; j <= 3 * w; j ++)
            b[j] = (b[j] + (LL)d * pf[j] % MOD) % MOD;
        multiply(pf, i);
    }
}

int main() {
    initIO();
    for (int bxlrz = 1; bxlrz <= T; bxlrz ++) {
        input();
        for (int i = 1; i <= n; i ++) solve(i);
        Lagrange();
        cout << "Case #" << bxlrz << ": ";
        for (int i = 1; i <= 3 * w; i ++) cout << b[i] << ' ';
        cout << '\n';
    }
    return 0;
}