首页 > 其他分享 >组合数学杂记

组合数学杂记

时间：2024-11-27 15:22:56浏览次数：10  
标签：return 组合 int sum 数学 inline 杂记 binom Mod

组合数学杂记

二项式系数

基本结论

对称恒等式：

\[\binom{n}{k} = \binom{n}{n - k} \]

加法公式：

\[\binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1} \]

对其对应多项式函数求导可以得到：

\[\sum_{i = 0}^n i \binom{n}{i} = n 2^{n - 1} \\ \sum_{i = 0}^n i^2 \binom{n}{i} = n (n + 1) 2^{n - 2} \]

吸收恒等式：

\[\binom{n}{k} = \frac{n}{k} \binom{n - 1}{k - 1} \\ k \binom{n}{k} = n \binom{n - 1}{k - 1} \]

三项恒等式：

\[\binom{a}{b} \binom{b}{c} = \binom{a}{c} \binom{a - c}{b - c} \]

与 Fibonacci 数列联系：

\[\sum_{i = 0}^n \binom{n - i}{i} = F_{n + 1} \]

与下降幂联系：

\[\frac{a^{\underline{i}}}{b^{\underline{i}}} = \frac{\binom{a}{i}}{\binom{b}{i}} = \frac{\binom {b - i}{b - a}}{\binom{b}{a}} \]

组合数求和

上指标求和

朱世杰恒等式：

\[\sum_{i = k}^n \dbinom{i}{k} = \dbinom{n + 1}{k + 1} \]

证明：在 \(n + 1\) 个球里拿 \(k + 1\) 个方案数为 \(\binom{n + 1}{k + 1}\) ，最后一个拿的是第 \(i + 1\) 个，对应方案数为 \(\binom{i}{k}\) 。

下指标求和

高橋君

\(m\) 次询问，每次给出 \(n, k\) ，求 \(\sum_{i = 0}^k \binom{n}{i}\) 。

\(n, m, k \leq 10^5\)

考虑莫队，记 \(f(n, k) = \sum_{i = 0}^k \binom{n}{i}\) ，分类讨论得到：

\[f(n, k + 1) = f(n, k) + \binom{n}{k + 1} \\ f(n, k - 1) = f(n, k) - \binom{n}{k} \\ f(n + 1, k) = 2 f(n, k) - \binom{n}{k} \\ f(n - 1, k) = \frac{f(n, k) + \binom{n - 1}{k}}{2} \]

时间复杂度 \(O(n \sqrt{n})\) 。

#include <bits/stdc++.h>
using namespace std;
const int Mod = 1e9 + 7;
const int N = 1e5 + 7;

struct Query {
    int n, k, bid, id;

    inline bool operator < (const Query &rhs) const {
        return bid == rhs.bid ? (bid & 1 ? k > rhs.k : k < rhs.k) : n < rhs.n;
    }
} qry[N];

int fac[N], inv[N], invfac[N], ans[N];

int m;

template <class T = int>
inline T read() {
    char c = getchar();
    bool sign = (c == '-');
    
    while (c < '0' || c > '9')
        c = getchar(), sign |= (c == '-');
    
    T x = 0;
    
    while ('0' <= c && c <= '9')
        x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    
    return sign ? (~x + 1) : x;
}

inline int add(int x, int y) {
    x += y;
    
    if (x >= Mod)
        x -= Mod;
    
    return x;
}

inline int dec(int x, int y) {
    x -= y;
    
    if (x < 0)
        x += Mod;
    
    return x;
}

inline void prework() {
    fac[0] = fac[1] = 1;
    inv[0] = inv[1] = 1;
    invfac[0] = invfac[1] = 1;
    
    for (int i = 2; i < N; ++i) {
        fac[i] = 1ll * fac[i - 1] * i % Mod;
        inv[i] = 1ll * (Mod - Mod / i) * inv[Mod % i] % Mod;
        invfac[i] = 1ll * invfac[i - 1] * inv[i] % Mod;
    }
}

inline int C(int n, int m) {
    return m > n ? 0 : 1ll * fac[n] * invfac[m] % Mod * invfac[n - m] % Mod;
}

signed main() {
    prework();
    m = read();

    for (int i = 1; i <= m; ++i)
        qry[i].n = read(), qry[i].k = read(), qry[i].bid = qry[i].n / 300, qry[i].id = i;

    sort(qry + 1, qry + 1 + m);
    int n = 1, k = 0, result = 1;

    for (int i = 1; i <= m; ++i) {
        for (; n < qry[i].n; ++n) // f(n, k) -> f(n + 1, k)
            result = dec(2ll * result % Mod, C(n, k));

        for (; n > qry[i].n; --n) // f(n, k) -> f(n - 1, k)
            result = 1ll * inv[2] * add(result, C(n - 1, k)) % Mod;

        for (; k < qry[i].k; ++k) // f(n, k) -> f(n, k + 1)
            result = add(result, C(n, k + 1));

        for (; k > qry[i].k; --k) // f(n, k) -> f(n, k - 1)
            result = dec(result, C(n, k));

        ans[qry[i].id] = result;
    }

    for (int i = 1; i <= m; ++i)
        printf("%d\n", ans[i]);

    return 0;
}

平行求和法

\[\sum_{i = 0}^k \binom{n + i}{i} = \sum_{i = 0}^k \binom{n + i}{n} = \binom{n + k + 1}{n + 1} \]

二项式定理

\[(a + b)^n = \sum_{i = 0}^n \binom{n}{i} a^{n - i} b^i \]

取 \(a = b = 1\) 得到：

\[\sum_{i = 0}^n \binom{n}{i} = 2^n \]

取 \(a = 1, b = -1\) 得到：

\[\sum_{i = 0}^n (-1)^i \binom{n}{i} = [n = 0] \]

CF660E Different Subsets For All Tuples

有一个长度为 \(n\) 的数列，每个位置上的值在 \([1, m]\) 范围内。对于所有 \(m^n\) 个序列，求每个数列中本质不同的子序列个数（包含空序列），然后求和 \(\bmod 10^9 + 7\) 。

\(n, m \leq 10^6\)

考虑统计每个子序列的出现次数（第一次），枚举子序列长度 \(i\) 与末尾位置 \(j\) ，前 \(j\) 个位置每一个不在子序列中的位置都不能与右边第一个在子序列中的位置相同，于是得到：

\[\begin{align} &\sum_{i = 1}^n \sum_{j = i}^n \binom{j - 1}{i - 1} m^{n - j + i} (m - 1)^{j - i} \\ =& \sum_{j = 0}^{n - 1} \sum_{i = 0}^j \binom{j}{i} m^{n - j + i} (m - 1)^{j - i} \\ =& \sum_{j = 0}^{n - 1} m^{n - j} \sum_{i = 0}^j \binom{j}{i} m^i (m - 1)^{j - i} \\ =& \sum_{i = 0}^{n - 1} m^{n - i} (2m - 1)^i \end{align} \]

#include <bits/stdc++.h>
using namespace std;
const int Mod = 1e9 + 7;
const int N = 1e6 + 7;

int n, m;

inline int mi(int a, int b) {
    int res = 1;
    
    for (; b; b >>= 1, a = 1ll * a * a % Mod)
        if (b & 1)
            res = 1ll * res * a % Mod;
    
    return res;
}

signed main() {
    scanf("%d%d", &n, &m);
    int ans = mi(m, n);

    for (int i = 0; i < n; ++i)
        ans = (ans + 1ll * mi(m, n - i) * mi(m * 2 - 1, i) % Mod) % Mod;

    printf("%d", ans);
    return 0;
}

范德蒙德卷积

\[\sum_{i = 0}^m \binom{n}{i} \binom{m}{k - i} = \binom{n + m}{k} \]

证明：

\[\begin{align} \sum_{k = 0}^{n + m} \binom{n + m}{k} x^k &= (x + 1)^{n + m} \\ &= (x + 1)^n (x + 1)^m \\ &= \sum_{r = 0}^n \binom{n}{r} x^r \sum_{s = 0}^m \binom{m}{s} x^s \\ &= \sum{k = 0}^{n + m} \sum_{r = 0}^k \binom{n}{r} \binom{m}{k - r} x^k \end{align} \]

一般化的式子：

\[\sum_{i = -r}^s \binom{n}{r + i} \binom{m}{s - i} = \binom{n + m}{r + s} \]

可以得到以下推论：

\[\sum_{i = 0}^{n} \binom{n}{i}^2 = \binom{2n}{n} \]

证明：\(\sum_{i = 0}^n \binom{n}{i}^2 = \sum_{i = 0}^n \binom{n}{i} \binom{n}{n - i} = \binom{2n}{n}\) 。

\[\sum_{i = 1}^n \dbinom{n}{i} \dbinom{n}{i - 1} = \dbinom{2n}{n - 1} \]

证明：

\[\begin{align} \sum_{i = 1}^n \binom{n}{i} \binom{n}{i - 1} &= \sum_{i = 0}^{n - 1} \binom{n}{i + 1} \binom{n}{i} \\ &= \sum_{i = 0}^{i - 1} \binom{n}{n - i - 1} \binom{n}{i} \\ &= \binom{2n}{n - 1} \end{align} \]

\[\sum_{i = 0}^m \binom{n}{i} \binom{m}{i} = \binom{n + m}{m} \]

证明：\(\sum_{i = 0}^m \binom{n}{i} \binom{m}{i} = \sum_{i = 0}^m \binom{n}{i} \binom{m}{m - i} = \binom{n + m}{m}\) 。

容斥原理

普通形式

\[|\bigcup_{i \in S} A_i| = \sum_{T \subseteq S, T \neq \emptyset} (-1)^{|T| - 1} |\bigcap_{j \in T} A_j| \]

一个简单的应用是：形如给出若干组限制，求满足所有限制方案数，大部分考虑容斥。即算出钦定违反 \(k\) 条限制的方案数（这些方案之间可能会有重叠），乘以容斥系数 \((-1)^k\) 并求和。

Min-Max 容斥

最值形式：

\[\max(S) = \sum_{T \subseteq S} (-1)^{|T| + 1} \min(T) \\ \min(S) = \sum_{T \subseteq S} (-1)^{|T| + 1} \max(T) \]

第 \(k\) 大/小值形式：

\[\max_k (S) = \sum_{T \subseteq S} (-1)^{|T| - k} \binom{|T| - 1}{k - 1} \min(T) \\ \min_k(S) = \sum_{T \subseteq S} (-1)^{|T| - k} \binom{|T| - 1}{k - 1} \max(T) \]

值得注意的是，Min-Max 容斥在期望下也是成立的。一般情况下，求期望的最大/最小值并不好求，但是若最大/最小值有一个好求，那么就可以用 Min-Max 容斥求出另一个。

P5643 [PKUWC2018] 随机游走

给出一棵树，每次等概率随机走到一个相邻点。\(q\) 次询问，每次给出一个集合 \(S\) ，求从 \(x\) （一开始就固定）出发随机游走直到点集 \(S\) 中所有点都至少经过一次的话，期望游走几步。特别地，点 \(x\) 视为一开始就被经过了一次。

\(n \leq 18\) ，\(q \leq 5000\)

求经过 \(S\) 里所有元素的期望时间，即到达 \(S\) 中最后一个点的期望步数（ \(\max\) ），那么可以转化为枚举 \(S\) 的子集 \(T\) ，求到达 \(T\) 中第一个元素的期望时间（ \(\min\) ）。

设 \(f_{u, S}\) 表示 \(u\) 第一次走到 \(S\) 中的点的期望步数，\(d_u\) 表示 \(u\) 的度数，则：

\[f_{u, S} = \frac{f_{fa_u, S} + \sum_{v \in son(u)} f_{v, S}}{d_u} + 1 \quad (x \not \in S) \\ f_{u, S} = 0 \quad (x \in S) \]

考虑将每个点的值都写作 \(f_{u, S} = k_u \times f_{fa_u, S} + b_u\) 的形式，记：

\[K_u = \sum_{v \in son(u)} k_v, B_u = \sum_{v \in son(u)} b_v \]

则得到：

\[f_{u, S} = \dfrac{1}{d_u - K_u} \times f_{fa_u, S} + \dfrac{d_u + B_u}{d_u - K_u} \]

即：

\[k_u = \dfrac{1}{d_u - K_u}, b_u = \dfrac{d_u + B_u}{d_u - K_u} \]

答案即为 \(\sum_{T \subseteq S} (-1)^{|T| + 1} f_{r, T}\) ，不难用高维前缀和预处理后 \(O(1)\) 查询。时间复杂度 \(O(n 2^n + q)\) 。

#include <bits/stdc++.h>
using namespace std;
const int Mod = 998244353;
const int N = 19;

struct Graph {
    vector<int> e[N];
    
    inline void insert(int u, int v) {
        e[u].emplace_back(v);
    }
} G;

int f[1 << N], g[1 << N];
int deg[N];

int n, q, r;

template <class T = int>
inline T read() {
    char c = getchar();
    bool sign = (c == '-');
    
    while (c < '0' || c > '9')
        c = getchar(), sign |= (c == '-');
    
    T x = 0;
    
    while ('0' <= c && c <= '9')
        x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    
    return sign ? (~x + 1) : x;
}

inline int add(int x, int y) {
    x += y;
    
    if (x >= Mod)
        x -= Mod;
    
    return x;
}

inline int dec(int x, int y) {
    x -= y;
    
    if (x < 0)
        x += Mod;
    
    return x;
}

inline int mi(int a, int b) {
    int res = 1;
    
    for (; b; b >>= 1, a = 1ll * a * a % Mod)
        if (b & 1)
            res = 1ll * res * a % Mod;
    
    return res;
}

inline int sgn(int n) {
    return n & 1 ? Mod - 1 : 1;
}

struct Node {
    int k, b;

    inline Node(const int _b = 0) : k(0), b(_b) {}

    inline Node(const int _k, const int _b) : k(_k), b(_b) {}

    inline Node operator + (const Node &rhs) const {
        return Node(add(k, rhs.k), add(b, rhs.b));
    }
} nd[N];

void dfs(int u, int f, int state) {
    Node res = 0;

    for (int v : G.e[u])
        if (v != f)
            dfs(v, u, state), res = res + nd[v];

    if (~state >> u & 1) {
        nd[u].k = mi(dec(deg[u], res.k), Mod - 2);
        nd[u].b = 1ll * add(deg[u], res.b) * nd[u].k % Mod;
    } else
        nd[u] = 0;
}

signed main() {
    n = read(), q = read(), r = read() - 1;

    for (int i = 1; i < n; ++i) {
        int u = read() - 1, v = read() - 1;
        G.insert(u, v), G.insert(v, u);
        ++deg[u], ++deg[v];
    }

    for (int i = 1; i < (1 << n); ++i)
        dfs(r, -1, i), f[i] = 1ll * nd[r].b * sgn(__builtin_popcount(i) + 1) % Mod;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < (1 << n); ++j)
            if (j >> i & 1)
                f[j] = add(f[j], f[j ^ (1 << i)]);

    while (q--) {
        int k = read(), state = 0;

        while (k--)
            state |= 1 << (read() - 1);

        printf("%d\n", f[state]);
    }

    return 0;
}

P3175 [HAOI2015] 按位或

有一个 \(n\) 位二进制数 \(x\) ，初始为 \(0\) ，每次有 \(p_i\) 的概率令 \(x \gets x \operatorname{or} i\) ，求 \(x = 2^n - 1\) 的期望次数。

\(n \leq 20\)

将其转化为枚举子集 \(T\) 求 \(T\) 中元素出现一个 \(1\) 的期望，由离散随机变量的几何分布得到该值为 \(\frac{1}{p_T}\) 。求 \(p_T\) 做一遍高位前缀和就好了。

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-12;
const int N = 21;

double p[1 << N];

int n;

signed main() {
    scanf("%d", &n);
    int all = (1 << n) - 1;

    for (int i = 0; i <= all; ++i)
        scanf("%lf", p + i);

    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= all; ++j)
            if (j >> i & 1)
                p[j] += p[j ^ (1 << i)];

    double ans = 0;

    for (int i = 1; i <= all; ++i) {
        if (1 - p[all ^ i] < eps)
            return puts("INF"), 0;

        ans += (__builtin_parity(i) ? 1 : -1) / (1 - p[all ^ i]);
    }

    printf("%.6lf", ans);
    return 0;
}

P4707 重返现世

每秒按固定概率出现物品，求收集到 \(k\) 种物品的期望时间。

\(n \leq 1000\) ，\(n - k \leq 10\)

先令 \(k \gets n - k + 1\) ，将问题转化为 \(\max_k\) ，此时 \(k \leq 11\) 。

考虑 Min-Max 容斥：\(E(\max_k(S)) = \sum_{T \subseteq S} (-1)^{|T| - k} \binom{|T| - 1}{k - 1} E(\min(T))\) 。设 \(f_{i, j, k}\) 表示前 \(i\) 个位置，目前选出的物品 \(\sum p = j\) ，\(\sum_{T \subseteq S} (-1)^{|T| - k} \binom{|T| - 1}{k - 1}\) 的值。若不选 \(i\) ，则：\(f_{i, j, k} \gets f_{i - 1, j, k}\) 。否则加入 \(i\) 后 \(\sum_{T \subseteq S} (-1)^{|T| - k} \binom{|T| - 1}{k - 1}\) 会变为 \(\sum_{T \subseteq S} (-1)^{|T| - k + 1} \binom{|T|}{k - 1}\) （即 \(|T| \to |T| + 1\) ），考虑用加法公式展开：

\[\begin{align} &\sum_{T \subseteq S} (-1)^{|T| - k + 1} \binom{|T|}{k - 1} \\ =& \sum_{T \subseteq S} (-1)^{|T| - k + 1} \left( \binom{|T| - 1}{k - 1} + \binom{|T| - 1}{k - 2} \right) \\ =& \sum_{T \subseteq S} (-1)^{|T| - (k - 1)} \binom{|T| - 1}{k - 2} - \sum_{T \subseteq S} (-1)^{|T| - k} \binom{|T| - 1}{k - 1} \end{align} \]

于是可以得到：

\[f_{i, j, k} = f_{i - 1, j, k} + f_{i - 1, j - p_i, k - 1} - f_{i - 1, j - p_i, k} \]

初始时 \(f_{i, 0, 0} = 1\) ，时间复杂度 \(O(nmk)\) 。

#include <bits/stdc++.h>
using namespace std;
const int Mod = 998244353;
const int N = 1e3 + 7, M = 1e4 + 7, K = 1e1 + 7;

int p[N], inv[M], f[M][K], g[M][K];

int n, m, k;

inline int add(int x, int y) {
    x += y;
    
    if (x >= Mod)
        x -= Mod;
    
    return x;
}

inline int dec(int x, int y) {
    x -= y;
    
    if (x < 0)
        x += Mod;
    
    return x;
}

inline void prework(int m) {
    inv[0] = inv[1] = 1;

    for (int i = 2; i <= m; ++i)
        inv[i] = 1ll * (Mod - Mod / i) * inv[Mod % i] % Mod;
}

signed main() {
    scanf("%d%d%d", &n, &k, &m);
    k = n - k + 1, prework(m);

    for (int i = 1; i <= n; ++i)
        scanf("%d", p + i);

    f[0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        memcpy(g, f, sizeof(f));

        for (int j = p[i]; j <= m; ++j)
            for (int l = 1; l <= k; ++l)
                f[j][l] = add(f[j][l], dec(g[j - p[i]][l - 1], g[j - p[i]][l]));
    }

    int ans = 0;

    for (int i = 1; i <= m; ++i)
        ans = add(ans, 1ll * f[i][k] * m % Mod * inv[i] % Mod);

    printf("%d", ans);
    return 0;
}

反演相关

反演：两个函数（数列）之间的双向（求和）关系。

如：已知 \(F = A \times G\) ，其中 \(A\) 为关系矩阵，即 \(F_n = \sum_{i = 0} A_{n, i} G_i\) ，则可以得到 \(G = A^{-1} \times F\) 。事实上有定理：两个互为反演的关系矩阵互逆。

二项式反演

形式一

\[f(n) = \sum_{i = 0}^n (-1)^i \binom{n}{i} g(i) \iff g(n) = \sum_{i = 0}^n (-1)^i \binom{n}{i} f(i) \]

非常对称的形式。

形式二

\[f(n) = \sum_{i = n}^m (-1)^i \binom{i}{n} g(i) \iff g(n) = \sum_{i = n}^m (-1)^i \binom{i}{n} f(i) \]

上下指标互换，同样非常对称的形式。

形式三

\[f(n) = \sum_{i = 0}^n \dbinom{n}{i} g(i) \iff g(n) = \sum_{i = 0}^n (-1)^{n - i} \dbinom{n}{i} f(i) \]

记 \(f(n)\) 表示从 \(n\) 个不同元素中钦定若干个元素满足条件的方案数，\(g(n)\) 表示 \(n\) 个不同元素均满足条件的方案数。

这个形式可以实现 \(f, g\) 的互推，事实上右边可以理解为钦定 \(n - i\) 个元素不满足条件。

形式四

\[f(n) = \sum_{i = n}^m \dbinom{i}{n} g(i) \iff g(n) = \sum_{i = n}^m (-1)^{i - n} \dbinom{i}{n} f(i) \]

形式三上下指标互换的推论。把组合数拆开看看：

\[g_n = \sum_{i = n}^m (-1)^{i - n} \frac{i!}{n! (n - i)!} f_i \\ g_n = \frac{1}{n!} \sum_{i = n}^m \frac{(-1)^{i - n}}{(i - n)!} \times i! f_i \]

用 NTT 计算差卷积即可做到 \(O(n \log n)\) 。计算差卷积只要先 reverse 一下，最后再 reverse 回来即可。

P4491 [HAOI2018] 染色

有一个长度为 \(n\) 的序列，可以给每个位置染上 \([1, m]\) 的颜色。若恰好出现 \(S\) 次的颜色有 \(k\) 种，则会获得 \(w_k\) 的价值。求所有染色方案的价值和。

\(n \leq 10^7\) ，\(m \leq 10^5\) ，\(S \leq 150\)

不难发现当 \(k > \min(m, \lfloor \frac{n}{s} \rfloor)\) 时 \(w_k\) 不会被统计，下令 \(n = \min(m, \lfloor \frac{n}{s} \rfloor)\) 。

考虑容斥，钦定 \(k\) 种颜色染 \(S\) 次，则：

\[f(k) = \binom{m}{k} \times \frac{n!}{(S!)^k (n - kS)!} \times (n - kS)^{m - k} \]

不难发现这个会算重，设恰好出现 \(S\) 次的颜色有 \(k\) 种的方案数为 \(g(k)\) ，则不难得到：

\[f(k) = \sum_{i = k}^n \binom{i}{k} g_i \]

二项式反演得到：

\[g(k) = \sum_{i = k}^n (-1)^{i - k} \binom{i}{k} f_i \]

NTT 做差卷积即可。

#include <bits/stdc++.h>
using namespace std;
const int Mod = 1004535809;
const int N = 1e7 + 7, M = 1e5 + 7;

int fac[N], inv[N], invfac[N];
int a[M], f[M], g[M], h[M];

int n, m, s;

template <class T = int>
inline T read() {
    char c = getchar();
    bool sign = (c == '-');
    
    while (c < '0' || c > '9')
        c = getchar(), sign |= (c == '-');
    
    T x = 0;
    
    while ('0' <= c && c <= '9')
        x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    
    return sign ? (~x + 1) : x;
}

inline int add(int x, int y) {
    x += y;
    
    if (x >= Mod)
        x -= Mod;
    
    return x;
}

inline int dec(int x, int y) {
    x -= y;
    
    if (x < 0)
        x += Mod;
    
    return x;
}

inline int mi(int a, int b) {
    int res = 1;
    
    for (; b; b >>= 1, a = 1ll * a * a % Mod)
        if (b & 1)
            res = 1ll * res * a % Mod;
    
    return res;
}

inline int sgn(int n) {
    return n & 1 ? Mod - 1 : 1;
}

inline void prework() {
    fac[0] = fac[1] = 1;
    inv[0] = inv[1] = 1;
    invfac[0] = invfac[1] = 1;
    
    for (int i = 2; i < N; ++i) {
        fac[i] = 1ll * fac[i - 1] * i % Mod;
        inv[i] = 1ll * (Mod - Mod / i) * inv[Mod % i] % Mod;
        invfac[i] = 1ll * invfac[i - 1] * inv[i] % Mod;
    }
}

inline int C(int n, int m) {
    return m > n ? 0 : 1ll * fac[n] * invfac[m] % Mod * invfac[n - m] % Mod;
}

namespace Poly {
#define cpy(f, g, n) memcpy(f, g, sizeof(int) * (n))
#define clr(f, n) memset(f, 0, sizeof(int) * (n))
const int rt = 3, invrt = 334845270;
const int S = 2e6 + 7;

int rev[S];

inline void calrev(int n) {
    for (int i = 1; i < n; ++i)
        rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? n >> 1 : 0);
}

inline int calc(int n) {
    int len = 1;

    while (len <= n)
        len <<= 1;

    return calrev(len), len;
}

inline void NTT(int *f, int n, int op) {
    for (int i = 0; i < n; ++i)
        if (i < rev[i])
            swap(f[i], f[rev[i]]);

    for (int k = 1; k < n; k <<= 1) {
        int tG = mi(op == 1 ? rt : invrt, (Mod - 1) / (k << 1));

        for (int i = 0; i < n; i += k << 1) {
            int buf = 1;

            for (int j = 0; j < k; ++j) {
                int fl = f[i + j], fr = 1ll * buf * f[i + j + k] % Mod;
                f[i + j] = add(fl, fr), f[i + j + k] = dec(fl, fr);
                buf = 1ll * buf * tG % Mod;
            }
        }
    }

    if (op == -1) {
        int invn = mi(n, Mod - 2);

        for (int i = 0; i < n; ++i)
            f[i] = 1ll * f[i] * invn % Mod;
    }
}

inline void Times(int *f, int *g, int n) {
    NTT(f, n, 1), NTT(g, n, 1);

    for (int i = 0; i < n; ++i)
        f[i] = 1ll * f[i] * g[i] % Mod;

    NTT(f, n, -1);
}

inline void Mul(int *f, int n, int *g, int m, int *res) {
    static int a[S], b[S];
    int len = calc(n + m - 1);
    cpy(a, f, n), clr(a + n, len - n);
    cpy(b, g, m), clr(b + m, len - m);
    Times(a, b, len), cpy(res, a, n + m - 1);
}
#undef cpy
#undef clr
} // namespace Poly

signed main() {
    prework();
    n = read(), m = read(), s = read();

    for (int i = 0; i <= m; ++i)
        a[i] = read();

    int lim = min(m, n / s);

    for (int i = 0; i <= lim; ++i) {
        f[i] = 1ll * C(m, i) * fac[n] % Mod * mi(invfac[s], i) % Mod * 
            invfac[n - s * i] % Mod * mi(m - i, n - s * i) % Mod * fac[i] % Mod;
        h[i] = 1ll * sgn(i) * invfac[i] % Mod;
    }

    reverse(f, f + lim + 1);
    Poly::Mul(f, lim + 1, h, lim + 1, g);
    reverse(g, g + lim + 1);
    int ans = 0;

    for (int i = 0; i <= lim; ++i)
        ans = add(ans, 1ll * g[i] * invfac[i] % Mod * a[i] % Mod);

    printf("%d", ans);
    return 0;
}

多元形式

\[f(n_1, n_2, \cdots, n_m) = \sum_{k_i = 0}^{n_i} \prod_{i = 1}^m \binom{n_i}{k_i} g(k_1, k_2, \cdots, k_m) \\ g(n_1, n_2, \cdots, n_m) = \sum_{k_i = 0}^{n_i} \prod_{i = 1}^m (-1)^{n_i - k_i} \binom{n_i}{k_i} f(k_1, k_2, \cdots, k_m) \]

子集反演

\[f(S) = \sum_{T \subseteq S} g(T) \iff g(S) = \sum_{T \subseteq S} (-1)^{|S| - |T|} f(T) \\ f(S) = \sum_{S \subseteq T} g(T) \iff g(S) = \sum_{S \subseteq T} (-1)^{|T| - |S|} f(T) \]

格路计数

无限制

记 \([a, b, c, d]\) 表示 \((a, b)\) 走到 \((c, d)\) 的路径数，则有：

\[[a, b, c, d] = \dbinom{c - a}{\frac{c - a + d - b}{2}} \]

证明：考虑有 \(x\) 步是往右上走，有 \(y\) 步是往右下走。则：

\[\begin{cases} a + x + y = c \\ b + x - y = d \end{cases} \]

解得：

\[\begin{cases} x = \dfrac{c - a + d - b}{2} \\ y = \dfrac{c - a + b - d}{2} \end{cases} \]

考虑到总共 \(c - a\) 步，其中放 \(x\) 个向右上走的，则：

\[[a, b, c, d] = \dbinom{c - a}{\frac{c - a + d - b}{2}} \]

inline int walk(int a, int b, int c, int d) {
    if (((c - a + d - b) & 1) || d - b > c - a || b - d > c - a)
        return 0;
    else
    	return C(c - a, (c - a + d - b) / 2);
}

一条直线

相交

记 \(<a, b, c, d, k>\) 表示 \((a, b)\) 走到 \((c, d)\) 且与直线 \(y = k\) 相交的路径数，则有：

\[<a, b, c, d, k> = [a, b, c, 2k - d] \]

证明：考虑所有 \((a, b) \to (c, 2k - d)\) 的路径，其必然与 \(y = k\) 有交点，取第一个交点出来，把之后的路线关于 \(y = k\) 对称一下就是到 \((c, d)\) 的一个与 \(y = k\) 相交的路线。即 \((a, b) \to (c, d)\) 与 \((a, b) \to (c, 2k - d)\) 的合法路径构成双射（与 \(y = k\) 相交）。

不相交

记 \(\{ a, b, c, d, k \}\) 表示 \((a, b)\) 走到 \((c, d)\) 且与直线 \(y = k\) 不相交的路径数，则有：

\[\{ a, b, c, d, k \} = [a, b, c, d] - [a, b, c, 2k - d] \]

两条直线

记：

  • \(f(a, b, k_1, k_2)\) 表示 \((0, 0)\) 走到 \((a, b)\) 且与直线 \(y = k_1\) 与 \(y = k_2\) 都不相交的路径数。
  • \(g(a, b, k_1, k_2)\) 表示 \((0, 0)\) 走到 \((a, b)\) 且与直线 \(y = k_1\) 相交而直线与 \(y = k_2\) 不相交的路径数。

则有：

\[f(a, b, k_1, k_2) = [0, 0, a, b] - <0, 0, a, b, k_2> - g(a, b, k_1, k_2) \\ g(a, b, k_1, k_2) = f(a, 2k_1 - b, 2k_1 - k_2, k_2) + g(a, b, 2k_1 - k_2, k_2) \]

证明：\(f\) 比较显然，考虑证明 \(g\) 。先让路径强制触碰 \(y = k_1\) ，将路径的第一个交点以后的部分对称。注意到对称点之后的红线碰到 \(y = k_2\) 是可以的，考虑加回来。它一定会先与直线 \(y = k_1\) 相交，然后跟 \(y = k_2\) 相交。那么把 \((0, 0)\) 也对称下来到 \((0, 2k_1)\) ，漏算的方案即为一条从 \((0, 2k_1)\) 到 \((a, 2k_1 - b)\) 且不能经过 \(y = k_3\) 而必须经过 \(y = k_2\) 的路径数。

然后为什么这个把问题规模缩小了呢?

考虑到两条直线间的距离每次都会扩大两倍，而直线太远的时候我们就可以不去考虑直线的影响，并且无法碰到 \(y = k_1\) 时就可以直接停止递归。

int f(int a, int b, int k1, int k2) { //不能碰 y = k1 和 y = k2
    if (a < -b || a < b)
        return 0;
    else
    	return dec(dec(walk(0, 0, a, b), walk(0, 0, a, 2 * k2 - b)), g(a, b, k1, k2));
}

int g(int a, int b, int k1, int k2) { //必须碰 y = k1 而不能碰 y = k2
    if (a < -b || a < b)
        return 0;
    else if (a < 2 * k1 - b || a < b - 2 * k1)
        return 0;
    else
    	return add(f(a, 2 * k1 - b, 2 * k1 - k2, k2), g(a, b, 2 * k1 - k2, k2));
}

当直线间的距离越大，计算越快，而距离太小的时候一般可以直接DP。复杂度期望是线性的。

常见数列

Catalan 数

以下看似毫不相关的问题均属于 Catalan 数列：

  • \(n\) 个节点构成的无标号、区分左右儿子的二叉树数量为 \(Cat_n\) 。
  • \(n\) 个节点构成的无标号、区分儿子的有根树数量为 \(Cat_{n - 1}\) 。
  • \(n\) 个左括号与 \(n\) 个右括号组成的合法序列有 \(Cat_n\) 种。
  • \(n\) 个元素按照大小进栈，合法的出栈序列有 \(Cat_n\) 种。
  • \(n\) 边凸多边形的三角剖分方案数为 \(Cat_{n - 2}\) 。
  • 从 \((0,0)\) 出发，每次沿正方向走，到达 \((n,n)\) 且不接触直线 \(y=x\) 的路径数量为 \(Cat_n\) 。
  • 以圆上的 \(2n\) 个点为端点，连互不相交的 \(n\) 条弦的方案数为 \(Cat_n\) 。
  • 将 \(1 \sim 2n\) 中的数不重不漏地填入 \(2 \times n\) 的矩阵，每个数字大于其左边和上面数字的方案数 \(Cat_n\) 。

Catalan 数列的前几项为：

\(Cat_0\) \(Cat_1\) \(Cat_2\) \(Cat_3\) \(Cat_4\) \(Cat_5\) \(\cdots\)
\(1\) \(1\) \(2\) \(5\) \(14\) \(42\) \(\cdots\)

常见求法：

\[\begin{align} Cat_n &= \frac{\binom{2n}{n}}{n + 1} & (n > 2) \\ Cat_n &= \binom{2n}{n} - \binom{2n}{n - 1} \\ Cat_n &= \frac{(4n - 2)Cat_{n - 1}}{n + 1} \\ Cat_n &= \sum_{i = 1}^n Cat_{i - 1} \times Cat_{n - i} & (n > 2) \end{align} \]

Bell 数

Bell 数列的前几项为：

\(B_0\) \(B_1\) \(B_2\) \(B_3\) \(B_4\) \(B_5\) \(\cdots\)
\(1\) \(1\) \(2\) \(5\) \(15\) \(52\) \(\cdots\)

常见求法：

\[\begin{align} B_n &= \sum_{k = 0}^n {n \brace k} \\ B_{n + 1} &= \sum_{k = 0}^n \dbinom{n}{k} B_k \end{align} \]

Fibonacci 数列

Fibonacci 数列的前几项为：

\(F_0\) \(F_1\) \(F_2\) \(F_3\) \(F_4\) \(F_5\) \(\cdots\)
\(0\) \(1\) \(1\) \(2\) \(3\) \(5\) \(\cdots\)

常见求法：

\[F_i = \begin{cases} 1 & (i \leq 2) \\ F_{i - 1} + F_{i - 2} & (i \geq 3) \end{cases} \\ F_i = \frac{1}{\sqrt{5}} \left( (\frac{1 + \sqrt{5}}{2})^n - (\frac{1 - \sqrt{5}}{2})^n \right) \\ \begin{cases} F_{2n} = F_n (2 F_{n + 1} - F_n) \\ F_{2n + 1} = F_{n + 1}^2 + F_n^2 \end{cases} \]

常用结论：

  • \(F_{n - 1} F_{n + 1} - F_n^2 = (-1)^n\) 。

  • \(F_{n + m} = F_{n} F_{m + 1} + F_{n - 1} F_m\) 。

    • 特殊情况：\(F_{2n} = F_n(F_{n + 1} + F_{n - 1})\) 。

  • \(n \mid m \iff F_n \mid F_m\) 。

  • \(\gcd(F_n, F_m) = F_{\gcd(n, m)}\) 。

  • 齐肯多夫定理：任何正整数都可以表示成若干个不连续的斐波那契数（不包括第一个斐波那契数）之和。

模 \(m\) 意义下 Fibonacci 数列的最小正周期被称为皮萨诺周期，相关结论：

  • 皮萨诺周期总是不超过 \(6m\) （\(m = 2 \times 5^k\) 时取等）。
  • Fibonacci 数列 \(\bmod 2\) 的最小正周期为 \(3\) 。
  • Fibonacci 数列 \(\bmod 5\) 的最小正周期为 \(20\) 。
  • Fibonacci 数列 \(\bmod p\) （ \(p\) 是素数且 \(p \equiv \pm 1 \pmod{5}\) ）的最小正周期是 \(p - 1\) 的因数。
  • Fibonacci 数列 \(\bmod p\) （ \(p\) 是素数且 \(p \equiv \pm 2 \pmod{5}\) ）的最小正周期是 \(2p + 2\) 的因数。

标签：return,组合,int,sum,数学,inline,杂记,binom,Mod
From： https://www.cnblogs.com/wshcl/p/18572361/CombinatorialMathematics

相关文章

  • 数学期望在算法中的应用
    数学期望在算法中的应用数学期望是概率论和统计学中的一个核心概念，主要用于描述所有数据的平均值或者是中心趋势。在计算机算法竞赛中，期望算法属于一个中高等难度的算法，在程序设计中发挥着至关重要的作用。在近些年的CSP/USACO等国际知名算法竞赛中，期望和期望动态规划等算法常......
  • Hive函数学习
    Hive函数学习SQL练习1、count(*)、count(1)、count('字段名')区别从执行结果来看count(*)包括了所有的列，相当于行数，在统计结果的时候，不会忽略列值为NULL最慢的count(1)包括了忽略所有列，用1代表代码行，在统计结果的时候，不会忽略列值为NULL最快的count......
  • “组块”是一个跨学科的概念，旨在通过对信息进行合理分解和组合，优化信息处理的效率。无
    “组块”一词在不同的领域有不同的含义。通常来说，组块（Chunking）是指将信息或数据分成较小的、易于处理和理解的部分。在认知心理学、语言学、计算机科学和学习理论中，组块都有各自的应用。1.认知心理学中的组块在认知心理学中，组块（Chunking）指的是通过将大量的信息划分成更小、更有......
  • 2024届新题型数学模拟选题
    目录#12024九省联考#2浙江省L16联盟2024年高三返校适应性测试#12024九省联考题型题号代数10,11,14几何8,18#2浙江省L16联盟2024年高三返校适应性测试题型题号代数8,9,11,19(1)几何16(1)(ii)......
  • go泛型函数学习
    01什么是泛型泛型类似C++中的模板Go是一门强类型语言，意味着程序中的每个变量和值都有某种特定的类型，例如int、string等。在函数签名中，我们需要对参数和返回值指定类型，如下所示：funcAdd(a,bint)int参数a和b的类型是int，返回值类型也是int，结果是a和b的和。对两......
  • 【网络系统管理】2023年全国职业院校技能大赛：组策略--10套题组合--4
    16、只有域管理员和IT部门员工可以登陆服务器（1）计算机配置\策略\Windows设置\安全设置\本地策略\用户权限分配17、创建ChinaSkills23为GPO管理员，加入到企业管理、域控管理员组（1）gpmc.msc\林\域\%domain%--在这个域中创建GPO18、为所有域用户设置漫游文件（1）用户和计算机\%do......
  • 实验4 类的组合、继承、模板类、标准库
    实验任务2：代码：GradeCalc.hpp1#include<iostream>2#include<vector>3#include<string>4#include<algorithm>5#include<numeric>6#include<iomanip>78usingstd::vector;9usingstd::string;10......
  • 实验四 类的组合、继承、模板类、标准库
    1、实验任务二GradeCalc.hpp#include<iostream>#include<vector>#include<string>#include<algorithm>#include<numeric>#include<iomanip>usingstd::vector;usingstd::string;usingstd::cin;usingstd::cout;usingstd......
  • 实验4 类的组合、继承、模板类、标准库
    实验任务2GradeCalc.hpp源码#include<iostream>#include<vector>#include<string>#include<algorithm>#include<numeric>#include<iomanip>usingstd::vector;usingstd::string;usingstd::cin;usingstd::cout;usingstd:......
  • 实验4 类的组合、继承、模板类、标准库
    task1：1.点击查看代码#include<iostream>usingstd::cout;usingstd::endl;//类A的定义classA{public:A(intx0,inty0);voiddisplay()const;private:intx,y;};A::A(intx0,inty0):x{x0},y{y0}{}voidA::display()const{c......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99