跳转至

分治NTT&分治+NTT

习题

P4721 【模板】分治 FFT - 洛谷

给定 \(g_1,g_2,…,g_{n-1}\)，求 \(f_0,f_1,…,f_{n-1}\)。

其中 \(f_i=\sum_{j=1}^if_{i-g}*g_j\)，f_0=1。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
{ 多项式基础模版 }
int n;
Poly<int> f, g;
void solve(int L, int R) {
    if (L == R) {
        if (L == 0) f[0] = 1;
        return;
    }
    int mid = L + R >> 1;
    solve(L, mid);
    Poly<Int> A(mid - L + 1);
    for (int i = L ; i <= mid ; i++) {
        A[i - L] = f[i];
    }
    Poly<Int> B(R - L + 1);
    for (int i = 0 ; i < R - L + 1 ; i++) {
        B[i] = g[i];
    }
    A = A * B;
    for (int i = mid + 1 ; i <= R ; i++) {
        f[i] = add(f[i], A[i - L]);
    }
    solve(mid + 1, R);
}
int main() {
    cin >> n;
    f.resize(n);
    g.resize(n + 1);
    for (int i = 1 ; i < n ; i++) {
        cin >> g[i];
    }
    solve(0, n - 1);
    cout << f;
    return 0;
}

P5644 [PKUWC2018] 猎人杀 - 洛谷

令 \(F(S)\) 为集合 \(S\) 中的猎人在 \(1\) 号猎人后面死的概率，\(G(S)\) 在 \(1\) 号猎人死后，猎人集合恰好为 \(S\) 的概率。

那么有 \(F(S)=\sum_{S\subseteq T}G(T)\)

由子集反演得 \(G(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}*F(T)\)

那么 \(G(\varnothing)=\sum_S(-1)^{|S|}*F(S)\)

\(F(S)=\sum_{i=0}^{+\infty}(\dfrac{w(U)-w_1-w(S)}{w(U)})^i*\dfrac{w_1}{w(U)}=\dfrac{w_1}{w_1+w(S)}\)

得 \(G(\varnothing)=\sum_S(-1)^{|S|}*\dfrac{w_1}{w_1+w(S)}\)

由于 \(w(S)\leq10^5\), 所以可以枚举 \(w(S)\)

得 \(G(\varnothing)=\sum_{w(S)=i}(-1)^{|S|}*\dfrac{w_1}{w_1+i}\)

然后转换成一个背包的无标号计数问题，对生成函数 \(1-w_i\) 进行分治NTT求解。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
{ 多项式模版 }
int w[100005];
vector<int> solve(int L, int R) {
    if (L == R) {
        Poly a(w[L] + 1);
        a[0] = 1;
        a[w[L]] = P - 1;
        return a;
    }
    int mid = L + R >> 1;
    return solve(L, mid) * solve(mid + 1, R);   
}
int main() {
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> w[i];
    }
    Poly res = solve(2, n);
    i64 ans = 0;
    for (int i = 0 ; i < (int) res.size() ; i++) {
        mod_add(ans, mod_mul_t(mod_mul_t(w[1], res[i]), qpow(i + w[1])));
    }
    cout << ans;
    return 0;
}

C-挑选队友

\(n\) 个人分成 \(m\) 个群, 要选 \(k\) 个人, 每个群至少选一人, 问选择方案数.

已知第 \(i\) 个群的生成函数为 \(\sum_{i=1}^{s_i}C_{s_i}^i*x^i\)

分治NTT 求出 \(m\) 个群的方案 \(F(x)\), \([x^k]F(x)\) 即为答案。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
{ 多项式模版 }
{ 组合数模版 }
int s[100005];
Poly solve(int L, int R) {
    if (L == R) {
        Poly r(s[L] + 1);
        for (int i = 1 ; i <= s[L] ; i++) {
            r[i] = C(s[L], i);
        }
        return r;
    }
    int mid = L + R >> 1;
    return solve(L, mid) * solve(mid + 1, R);
}
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1 ; i <= m ; i++) {
        cin >> s[i];
    }
    cout << solve(1, m)[k];
    return 0;
}