XCPC wiki - 组合数学 | 小明の雜貨屋

逆元

模为素数

constexpr int mod = 998244353;

ll qpow(ll a, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int inv(int n) {
    return qpow(n, mod - 2);
} // 1/a (p 是素数)

非固定模数

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) return x = 1, y = 0, a;
    ll d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

auto exexgcd(ll a, ll b, ll c) {
    ll d = gcd(a, b);
    if (c % d) return pair(-1, -1); // 无解
    ll x, y;
    a /= d, b /= d, c /= d;
    exgcd(a, b, x, y);
    x = ((x * c % b) + b * d) % b;
    y = (c - a * x) / b;
    return pair(x, y);
}
// 同余方程 ax == c (mod b) 的最小正整数解
// 即解不定方程 ax + by = c
// 调用 liEq(a,b,c);

int mod = 123456;

ll inv(ll a) {
    return liEq(a, mod, 1);
} // 1/a (mod 无限制)

组合数

$\begin{aligned} \operatorname{C}_{n}^{m} &= \frac{n (n-1) \cdots (n-m+1) } {m (m-1) \cdots 1} \\ \operatorname{C}_{n}^{m} &= \frac{n-m+1}{m}C_{n}^{m-1} \\ k\operatorname{C}_{n}^{k} &= n\operatorname{C}_{n-1}^{k-1} \\ \end{aligned}$

杨辉三角二维递推（使用于 $n$ 较小或模数不固定）

$C_n^m=C_{n-1}^{m}+C_{n-1}^{m-1}$

ll C[N][N];
void init(int n) {
    for (int i = 0; i <= n; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }    
}

在时间 $\Theta(n^2)$、空间 $\Theta(n^2)$ 内计算 $C_0^0 \sim C_n^n$。

预处理阶乘（万用方法，适用于 $n$ 较大）

constexpr int mod = 998244353;
constexpr int N = 1e6 + 8;
ll fac[N], ifac[N];

ll qpow(ll a, ll n) {
	ll res = 1;
	while (n) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

ll inv(ll n) {
	return qpow(n, mod - 2);
}

void init(int n) {
	fac[0] = ifac[0] = 1;
	for (int i = 1; i <= n; i++) {
		fac[i] = fac[i - 1] * i % mod;
	}
	ifac[n] = inv(fac[n]);
	for (int i = n; i > 0; i--) {
		ifac[i - 1] = ifac[i] * i % mod;
	}
}

ll C(int n, int m) {
	if (n < m || m < 0) return 0;
	return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
ll A(int n, int m) {
    return fac[n] * ifac[n - m] % mod;
}

在时空复杂度 $\Theta(n)$ 内计算 $\operatorname{C}{0}^{0} \sim \operatorname{C}{n}^{n}$。

卢卡斯定理（适用于 $p$ 较小）

对于 $m,n$ 和素数 $p$， $Cm^n\equiv\prod{i=0}^{k}C_{m_i}^{n_i}\pmod{p}$，其中 $m=m_kp^k+\cdots +m_1p+m_0,~n=n_kp^k+\cdots +n_1p+n_0$ 是 $m$ 和 $n$ 的 $p$ 进制展开。

$C_m^n\equiv C_{m\bmod p}^{n \bmod p}\cdot C_{\lfloor m/p\rfloor}^{\lfloor n/p\rfloor}\pmod{p}$

ll fac[N];
void dofac(int n, int p) {
	fac[0] = fac[1] = 1;
	for (int i = 2; i < n; ++i) fac[i] = fac[i - 1] * i % p;
}

ll inv[N];
ll doInv(ll a, ll p) {
	a %= p;
	if (a == 0) return -1;
	if (a == 1) return 1;
	if (inv[a]) return inv[a];
	return inv[a] = (p - p / a) * doInv(p % a, p) % p;
}

ll C(ll n, ll m, ll p) {
	return n < m ? 0 :
		fac[n] * doInv(fac[m], p) % p * doInv(fac[n - m], p) % p;
}

ll lucas(ll n, ll m, ll p) {
	return m == 0 ? 1 :
		lucas(n / p, m / p, p) * C(n % p, m % p, p) % p;
}

时间复杂度 $\Theta(p)$。

jiangly 组合数 (待修改)

struct Comb {
    int n;
    std::vector<ll> _fac;
    std::vector<ll> _invfac;
    std::vector<ll> _inv;
    
    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }
    
    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    Z binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb;

例题

2024 杭电多校 9001 - 树异或价值

[[../contests/2024 杭电多校 /2024-08-16：2024“钉耙编程”中国大学生算法设计超级联赛（9）|2024-08-16：2024“钉耙编程”中国大学生算法设计超级联赛（9）]]

题意求满足如下条件的 $a$ 数组的数量：

$\sum\limits{i=1}^n \sum\limits{j=1}^n\left(ai \oplus a_j\right) \times \operatorname{dep}{\operatorname{LCA}(i, j)}$ 最大；
$0 \leqslant a_{i} \leqslant 2^{k}-1$。

思路每位情况独立，现设 $k=1$。

原式等价于 $\sum\limits{x=1}^n \sum\limits{i,j \in \operatorname{subtree}(x)} \left(a_i \oplus a_j\right)$，表示树上所有点的子树内两两之间的异或值之和的和。这就将奇怪的问题转化为 子树问题，满足树形 DP 要求。

设 $f{u,d}$ 表示填完 $u$ 的子树后 $0$ 和 $1$ 的数量差为 $d$ 的方案数。由于 $a_i \in{0,1}$，希望子树内 $0$ 和 $1$ 的数量尽量接近。如果子树大小为偶数，则希望数量差为 $0$，只需考虑 $f{u,0}$，如果子树大小为奇数，希望是 $\pm 1$，且有 $f{u,1}=f{u,-1}$。因此我们 把第二维省略 ，设 $f{u}=f{u,0}$ 或 $f{u}=f{u,1}$。也就是说 只考虑 $\boldsymbol0$ 不比 $\boldsymbol1$ 少的情形。

设 $u$ 的子节点的子树中大小为奇数的儿子的数量有 $g{u}$ 个，不难发现 **$\boldsymbol {g{u}}$ 与 $\boldsymbol u$ 子树大小的奇偶性相反 **。分类讨论：

如果 $g_{u}$ 为奇数，为了使得 $0$ 和 $1$ 的数量恰好相等，

如果 $u$ 选择 $1$，则需要在 $u$ 的子节点 $v$ 中选择 $\frac{g{u}-1}{2}$ 个 $1$ 和 $\frac{g{u}+1}{2}$ 个 $0$；
如果 $u$ 选择 $0$，则需要选择 $\frac{g{u}-1}{2}$ 个 $0$ 和 $\frac{g{u}+1}{2}$ 个 $1$。

这种情况下，总共有 $h{u}=2\operatorname{C}{g{u}}^{g{u} /2}$ 种选法。

如果 $g_{u}$ 是偶数，为了使得 $0$ 和 $1$ 的数量之差为 $1$，

如果 $u$ 选择 $1$，则需要在 $u$ 的子节点 $v$ 中选择 $\frac{g{u}}{2}-1$ 个 $1$ 和 $\frac{g{u}}{2}+1$ 个 $0$；
如果 $u$ 选择 $0$，则需要选择 $\frac{g{u}}{2}$ 个 $1$ 和 $\frac{g{u}}{2}$ 个 $0$。

这种情况下，总共有 $h{u}=\operatorname{C}{g{u}}^{g{u} /2}+\operatorname{C}{g{u}}^{g_{u} /2-1}$ 种选法。

因此有 $f{u}=h{u}\cdot\prod f_{v}$，$f$ 数组可省略。

$k=1$ 的答案是 $\begin{cases}f{1,0}=f{1} ,& 2\mid n \f{1,1}+f{1,-1}=2f_{1} ,& 2\nmid n\end{cases}$。

int n, k;
cin >> n >> k;

vector<int> p(n + 1);
for (int u = 2; u <= n; ++u) cin >> p[u];

vector<int> g(n + 1);
Z f = 1;
for (int v = n; v; --v) {
    if (g[v] % 2 == 0) {
        f *= C(g[v], g[v] / 2 - 1) + C(g[v], g[v] / 2);
        g[p[v]]++;
    } else {
        f *= 2 * C(g[v], g[v] / 2);
    }
}
if (n % 2 == 1) f *= 2;

cout << qpow(f, k) << '\n';

2024 杭电多校 8005 - cats 的二分答案

constexpr int D = 60;
ll C[D + 1][D + 1];
void beforeT() {
    for (int i = 0; i <= D; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]);
    }
}

void eachT() {
    ll l = read(), r = read();
    int k = min((ll)D, read());

    ll n = r - l + 1;
    int m = __lg(n) + ((n & (n + 1)) == 0);  // 2^m-1 <= n < 2^(m+1)-1

    vector<ll> res(128);
    for (int i = 0; i < D; ++i) {
        res[i] += C[m][i + 1];
    }

    n -= (1ll << m) - 1;

    int st = 0;
    for (int bit = D; ~bit; --bit) {
        if (n & (1ll << bit)) {
            for (int i = 0; i <= bit; ++i) {
                res[st + i] += C[bit][i];
            }
            st += 1;
        }
    }

    ll ans = 0;
    for (int i = 0; i <= k; ++i) {
        ans += res[i];
    }
    printf("%lld\n", ans);
}

2024 杭电多校 1012 - 并

[[../contests/2024 杭电多校 /2024-07-19：2024“钉耙编程”中国大学生算法设计超级联赛（1）|2024-07-19：2024“钉耙编程”中国大学生算法设计超级联赛（1）]]

平面直角坐标系上有 $n$ 个矩形，其中第 $i$ 个的左上角坐标为 $(x{i,1},y{i,1})$，右下角坐标为 $(x{i,2},y{i,2})$。对于 $k \in [1,n]$，求解在 $n$ 个矩形中随机选取 $k$ 个不同的矩形，其所有覆盖部分的并集的面积的期望值。

数据范围：$n \leqslant 2 \times 10^3$。

暴力扫描每个位置有几个矩形覆盖，先离散化，记 $g_{i}$ 表示 $n$ 个矩形中有 $c$ 个矩形覆盖的面积和，$k$ 的答案为

$\sum_{i=1}^{n} \dfrac{(1-\operatorname{C}_{n-i}^{k})g_{i}}{\operatorname{C}_{n}^{k}}$

void eachT() {
    int n = read();

    vector<int> allx, ally;
    allx.push_back(0);
    ally.push_back(0);

    vector<array<int, 4>> f(n);
    for (auto& [x1, y1, x2, y2] : f) {
        x1 = read(), y1 = read(), x2 = read(), y2 = read();
        allx.push_back(x1);
        allx.push_back(x2);
        ally.push_back(y1);
        ally.push_back(y2);
    }
    sort(allx.begin(), allx.end());
    sort(ally.begin(), ally.end());
    allx.erase(unique(allx.begin(), allx.end()), allx.end());
    ally.erase(unique(ally.begin(), ally.end()), ally.end());

    int x = allx.size(), y = ally.size();
    vector w(x, vector<int>(y));
    for (auto& [x1, y1, x2, y2] : f) {
        x1 = lower_bound(allx.begin(), allx.end(), x1) - allx.begin();
        y1 = lower_bound(ally.begin(), ally.end(), y1) - ally.begin();
        x2 = lower_bound(allx.begin(), allx.end(), x2) - allx.begin();
        y2 = lower_bound(ally.begin(), ally.end(), y2) - ally.begin();
        ++w[x1][y1];
        --w[x2][y1];
        --w[x1][y2];
        ++w[x2][y2];
    }
    
    for (int i = 1; i < x; i++) {
        for (int j = 1; j < y; j++) {
            w[i][j] += w[i][j - 1];
        }
    }

    vector<Z> g(n + 1);
    for (int i = 1; i < x - 1; i++) {
        for (int j = 1; j < y - 1; j++) {
            w[i][j] += w[i - 1][j];
            g[w[i][j]] += 1ll * (allx[i + 1] - allx[i]) * (ally[j + 1] - ally[j]);
        }
    }

    Z sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += g[i];
    }

    for (int k = 1; k <= n; k++) {
        Z ans = 0;
        for (int i = 1; i <= n; i++) {
            ans -= C[n - i][k] * g[i];
        }
        ans /= C[n][k];
        ans += sum;
        cout << ans << endl;
    }
}

2024 杭电多校 5013 - 飞行棋

[[../contests/2024 杭电多校 /2024-08-02：2024“钉耙编程”中国大学生算法设计超级联赛（5）#5013 - 飞行棋 (50)|2024-08-02：2024“钉耙编程”中国大学生算法设计超级联赛（5）]]

有 $n + 1$ 个的格子编号 $0$ 到 $n$，$0$ 号格子为起点，$n$ 号格子为终点。花费 $1$ 的代价等概率随机 $[1,n]$ 中的一个整数 $x$，向终点走 $x$ 步，若达到终点还有剩余步数则反向行走。如果随机到了数字 $n$ 并且未抵达终点则赠送一次（即不花费代价）等概率随机 $[1,n - 1]$ 中整数 $y$ 的机会，并向终点走 $y$ 步，若达到终点还有剩余步数则反向行走。求能恰好抵达终点的代价的期望，对 $1000000007$ 取模。

方法一 设 $p_{i}$ 表示到达终点时代价为 $i$ 的概率，有

$p_{i}= \begin{cases} \displaystyle\frac{1}{n}, & i=1 \\ \displaystyle(1-p_{1}-p_{2}-\dots-p_{i-1})\Big(\frac{1}{n}+\frac{1}{n}\cdot\frac{1}{n-1}\Big),& i>1 \end{cases}$

计算得

$p_{i}= \begin{cases} \displaystyle \frac{1}{n}, & i=1 \\ \dfrac{(n-2)^{i-2}}{n(n-1)^{i-2}}, &i>1 \end{cases}$

因此答案为

$\frac{1}{n}+\frac{1}{n}\sum_{i=2}^{\infty}i\cdot\Big(\dfrac{n-2}{n-1}\Big)^{i-2}=n-1+\dfrac{1}{n}$

方法二 在 $0$ 号格时有 $\cfrac{1}{n}$ 的概率直接进入终点。对另外 $\cfrac{n-1}{n}$ 概率发生的情况，从 $1$ 号格到 $n-1$ 号格花费 $1$ 的代价进入终点的期望是相同的，都是 $\cfrac{1}{n-1}$，另外 $\cfrac{n-2}{n-1}$ 的概率继续停留在 $1 \sim n-1$ 号格内，故在这个问题上，位于 $1 \sim n-1$ 号格子上的状态都是等价的。所以期望花费的代价为

$1+\cfrac{n-1}{n} \cdot(n-1)=n-1+\dfrac{1}{n}$

2024 牛客多校 4J - Zero

[[../contests/2024 牛客多校 /2024-07-25：2024 牛客暑期多校训练营 4#*J - Zero|2024-07-25：2024 牛客暑期多校训练营 4]]

给出一个 01 带 $?$ 的串，$?$ 等概率变成 $0$ 或 $1$。一段连续相同数的贡献是区间和的 $p$ 次幂。问期望贡献和。

设 $f{i,j}$ 表示以第 $i$ 位为区间右端点，$p=j$ 的期望贡献和。因 $x^{0}=1$，故初始 $f{*,0}=1$，注意到 $(x+1)^{j}=\sum\operatorname{C}_{j}^{k}x^{k}$，有转移方程

$f_{i,j} \leftarrow \begin{cases} 0,&s_{i}=0 \\ \displaystyle\sum_{k=0}^{j} \operatorname{C}_{j}^{k}f_{i-1,k} ,&s_{i}=1 \\ \displaystyle \cfrac{1}{2}\sum_{k=0}^{j} \operatorname{C}_{j}^{k}f_{i-1,k},&s_{i}=? \end{cases}$

答案为 $\sum f_{*,k}$。时间复杂度 $\Theta(nk^{2})$。

using Z = ModInt<998244353>;
Z f[N][M];
void eachT() {
    int n, p;
    string s;
    cin >> n >> p >> s;
    s = ' ' + s;

    Z ans = 0;
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= p; j++) {
            for (int k = 0; k <= j; k++) {
                f[i][j] += C[j][k] * f[i - 1][k];
            }
            if (s[i] == '0') f[i][j] = 0;
            if (s[i] == '?') f[i][j] *= inv2;
        }
        f[i][0] += 1;
        ans += f[i][p];
    }
    cout << ans << "\n";
}

2024 牛客多校 1A - A Bit Common

[[../contests/2024 牛客多校 /2024-07-16：2024 牛客暑期多校训练营 1#A - A Bit Common|2024-07-16：2024 牛客暑期多校训练营 1]]

题意求有多少长为 $n$ 的元素是 $[0, 2^m)$ 的整数序列，满足存在一个非空子序列的 AND 和都是 1，答案对输入的正整数 $q$ 取模．

思路二进制最低位为 0 的数一定不在 AND 和是 1 的子序列里，这些数除了最低位都可以任选．

对于二进制最低位为 1 的数，如果存在一个子序列的 AND 和是 1，那么包含这个子序列的子序列的 AND 和也是 1，只要所有二进制最低位为 1 的数 AND 和是 1 就能满足条件．

记二进制最低位为 1 的数有 $k > 0$ 个，这些数除了最低位的 AND 和都要是 0，也就是每一位上这些数都至少有一个是 $1$．

总方案：

$\sum_{k=1}^{n}\operatorname{C}_{n}^{k}2^{(n-k)(m-1)}(2^{k}-1)^{m-1}$

2024 牛客多校 1B - A Bit More Common

[[../contests/2024 牛客多校 /2024-07-16：2024 牛客暑期多校训练营 1#*B - A Bit More Common|2024-07-16：2024 牛客暑期多校训练营 1]]

题意求有多少长为 $n$ 的元素是 $[0, 2^m)$ 的整数序列，满足存在两个不同的非空子序列的 AND 和是 $1$，答案对输入的正整数 $q$ 取模．

思路也就是说，从刚才找到的子序列中移除某个，剩下的子序列的 AND 和仍是 $1$．

考虑反面，移除任意一个，剩下的子序列的 AND 和都不是 $1$．因此，每个数应当包含至少一个 独一无二的 0（自己的这一位是 0，其它数的这一位都是 1）．

——止步于此——

难以直接计算，故递推．

设 $f_{i,j}$ 表示 $i$ 个数，共有 $j$ 个独一无二的 0 的方案数（显然，每一个独一无二的 0 只能属于一个数）．递推方程：

$f_{i,j}= \begin{cases} 1 & i=1 \\ i\cdot(f_{i,j-1}+f_{i-1,j-1}) & 1<i \leqslant j \\ 0&i>j \end{cases}$

反面的总方案：

$\sum_{k=2}^{n}\operatorname{C}_{n}^{k}2^{(n-k)(m-1)} \sum_{j=k}^{m-1}\operatorname{C}_{m-1}^{j}(2^{k}-k-1)^{m-1-j}$

注意 $k=1$ 是个特例，此时一定无解．

因此总方案：

$\sum_{k=2}^{n}\operatorname{C}_{n}^{k}2^{(n-k)(m-1)} \left[(2^{k}-1)^{m-1}-\sum_{j=k}^{m-1}\operatorname{C}_{m-1}^{j}f_{k,j}\cdot(2^{k}-k-1)^{m-1-j} \right]$

核心代码：

ll ans = 0;
for (int k = 2; k <= n; ++k) {
    ll res = 0;
    for (int j = k; j <= m - 1; ++j) {
        res += C[m - 1][j] * f[k][j] % MOD
            * qpow(qpow(2, k, MOD) - k - 1 + MOD, m - 1 - j, MOD) % MOD;
        res %= MOD;
    }
    res = qpow(qpow(2, k, MOD) - 1, m - 1, MOD) % MOD - res;
    res = (res % MOD + MOD) % MOD;
    ans += C[n][k]
        * qpow(2, (m - 1) * (n - k), MOD) % MOD
        * res % MOD;
    ans %= MOD;
}
printf("%lld\n", ans);

时间复杂度已经达到 $\Theta(mn\log^{2} N)$，应当优化快速幂．

#include <cstdio>
using ll = long long;
inline ll read() {
    ll S = 0, C = 0; char Y = getchar();
    while (Y > 57 || Y < 48) C |= Y == 45, Y = getchar();
    while (Y <= 57 && Y >= 48) S = (S << 3) + (S << 1) + Y - 48, Y = getchar();
    return C ? -S : S;
}

inline ll qpow(ll S, ll Y, ll MOD) {
    ll C = 1;
    while (Y) {
        if (Y & 1) C = C * S % MOD;
        S = S * S % MOD;
        Y >>= 1;
    }
    return C;
}

const int N = 5000 + 8;
ll C[N][N], f[N][N];
ll pow2[N];

int main() {
    ll n = read(), m = read(), MOD = read();

    for (int i = 0; i < N; ++i) {
        C[i][0] = 1; C[i][i] = 1;
        for (int j = 1; j < i; ++j)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
    }

    for (int j = 1; j <= m - 1; ++j) {
        f[1][j] = 1;
    }
    for (int i = 2; i <= n; ++i) {
        for (int j = i; j <= m - 1; ++j) {
            f[i][j] = i * (f[i][j - 1] + f[i - 1][j - 1]) % MOD;
        }
    }

    ll ans = 0;
    pow2[1] = 2;
    for (int k = 2; k <= n; ++k) {
        pow2[k] = pow2[k - 1] * 2 % MOD;
        ll res = 0;
        for (int j = k; j <= m - 1; ++j) {
            res += C[m - 1][j] * f[k][j] % MOD
                * qpow(pow2[k] - k - 1 + MOD, m - 1 - j, MOD) % MOD;
            res %= MOD;
        }
        res = qpow(pow2[k] - 1, m - 1, MOD) % MOD - res;
        res = (res % MOD + MOD) % MOD;
        ans += C[n][k]
            * qpow(2, (m - 1) * (n - k), MOD) % MOD
            * res % MOD;
        ans %= MOD;
    }
    printf("%lld\n", ans);

    return 0;
}

VJwin4M - Lengthening Sticks - UPSOLVE (2100)

题意给出三根木棍的长度 $a,~b,~c$，可以给这三根木棍增加一些长度，长度是非负整数且总和不超过 $L$，求增加后这三根木棍可构成的非退化三角形的方法数。

换言之，确定数对 $(\Delta{a},~\Delta{b},~\Delta{c})$ 的组数，使得下式成立：

$\begin{cases} a+\Delta{a}<b+\Delta{b}+c+\Delta{c}\\ b+\Delta{b}<a+\Delta{a}+c+\Delta{c}\\ c+\Delta{c}<a+\Delta{a}+b+\Delta{b}\\ \Delta{a}+\Delta{b}+\Delta{c} \leqslant l \end{cases}$

输入只有四个数，输出只有一个数，这道题一定非！常！简！单！
而且是 A 题哦～~~（不告诉你是 Div1 的）~~

思路一 既然是数学题那当然要用数学的方法了：从反面考虑，所求方法数是总方法数减去不合法的方法数。

引理一 将 $m$ 个相同的球放到 $n$ 个不同的盒子（允许空）中的方法数为 $C_{m+n-1}^{n-1}$。利用插板法，这是熟知的结论。
引理二 $\sum\limits{k=0}^{n}C{k+m}^{m}=C_{n+m+1}^{m+1}$。
下文会频繁用到这两个结果，请留意。

$\mathbb{Step1}\quad$ 总方法数为 $\sum\limits{k=0}^{L}C{k+2}^{2}=C_{L+3}^{3}$，表示枚举将 $k\in\left[0,L\right]\cap\mathbb{Z}$ 个棍子分给三个盒子 $a,b,c$ 。事实上，它与将 $L$ 个棍子分给四个盒子等价，这四个盒子分别是 $a,b,c$ 和未使用。

$\mathbb{Step2}\quad$ 不合法即是一边大于等于另两边之和。

若操作后 $a$ 为最长边，即 $a’\geqslant b’+c’$。

此时枚举分给 $a$ 的棍子 $i=\Delta a$ 的上界依旧是 $i\leqslant L$，但下界需要更改为 $i\geqslant b+c-a$（这是由于 $a+\Delta a=a’\geqslant b’+c’\geqslant b+c$），当然，下界不能为负数，故确切的下界为 $i\geqslant \max{(0,~b+c-a)}$。

剩下 $j=L-i$ 个棍子分给 $b$ 和 $c$，即 $j=\Delta b+\Delta c$。首先注意，棍子数 $j$ 不能超过 $a+i-b-c$，这是由于 $a+i=a’\geqslant b’+c’=b+c+\Delta b+\Delta c=b+c+j$。因此，$0\leqslant j\leqslant\min{\big(L-i,~a+i-b-c)\big)}$。由引理，对每个确定的 $i$，方法数为

$\sum\limits_{j=0}^{\min{\big(L-i,~a+i-b-c)\big)}}C_{j+1}^{1}=C_{\min{\big(L-i,~a+i-b-c)\big)}+2}^{2}$

对 $i,~j$ 求和即得此时的方法数为

$\sum\limits_{i=\max{(0,~b+c-a)}}^{L}C_{\min{\big(L-i,~a+i-b-c)\big)}+2}^{2}=?$

$\mathbb{Step3}\quad$ 这个结果太丑了，我们希望使用数学知识加以化简，尤其是去掉 $\sum$。先看右边的 $\rm min$，它是关于 $i$ 的两个一次函数的最小值，图像应当是一条折线。那么结果即是

$\begin{align} S=C_{L+3}^{3} &-\sum\limits_{k=\max{(0,~b+c-a)}}^{L}C_{\min{\big(L-k,~k-(b+c-a)\big)}+2}^{2} \\ &-\sum\limits_{k=\max{(0,~c+a-b)}}^{L}C_{\min{\big(L-k,~k-(c+a-b)\big)}+2}^{2} \\ &-\sum\limits_{k=\max{(0,~a+b-c)}}^{L}C_{\min{\big(L-k,~k-(a+b-c)\big)}+2}^{2} \\ \end{align}$

思路二 依旧是数学方法，但是从正面考虑

设 $a,~b,~c$ 的增量分别为 $\Delta{a},~\Delta{b},~\Delta{c}$，并令 $m=c-a-b,n=b-a-c,p=a-b-c$，则

$\begin{cases} a+\Delta{a}<b+\Delta{b}+c+\Delta{c}\\ b+\Delta{b}<a+\Delta{a}+c+\Delta{c}\\ c+\Delta{c}<a+\Delta{a}+b+\Delta{b}\\ \Delta{a}+\Delta{b}+\Delta{c} \leqslant l \end{cases} \iff \begin{cases} \Delta{a}+\Delta{b}-\Delta{c}>m\\ \Delta{a}+\Delta{c}-\Delta{b}>n\\ \Delta{b}+\Delta{c}-\Delta{a}>p\\ \Delta{a}+\Delta{b}+\Delta{c} \leqslant l \end{cases}$

令 $w=\Delta{a}-\Delta{b},s=\Delta{a}+\Delta{b}$，且 $w,s$ 的奇偶性一致。

我们枚举 $w$，计算在每个 $w$ 下有多少种方法。

那么有 $\Delta{c}>\max(n-w,p+w)$

因为 $\Delta{a},\Delta{b}\geqslant0$，所以 $|w|\leqslant s\leqslant l-\Delta{c}$

接下来考虑把答案分成两部分来计算

第一部分是 $s\geqslant\lceil \frac{l+m+1}{2}\rceil$，这个时候 $\Delta{a}+\Delta{b}+\Delta{c}\leqslant l$ 的限制比 $\Delta{a}+\Delta{b}-\Delta{c}\geqslant m+1$ 的限制更紧

因为 $\Delta{a}=\frac{s+w}{2},\Delta{b}=\frac{s-w}{2}$，所以

那么就是一个等差数列求和的形式了，首项与公差为 $1$，项数就是 $\frac{l-\max(n-w,p+w)-\max(\lceil \frac{l+m+1}{2}\rceil,|w|))}{2}$ 但由于奇偶需要一致，所以需要微调一下，详见代码

第二部分是 $s\leqslant$ 刚才那个值，这个时候 $\Delta{a}+\Delta{b}-\Delta{c}\geqslant m+1$ 的限制更紧，求答案总数的方法同上。

2024 杭电多校 1005 - 博弈

[[../contests/2024 杭电多校 /2024-07-19：2024“钉耙编程”中国大学生算法设计超级联赛（1）|2024-07-19：2024“钉耙编程”中国大学生算法设计超级联赛（1）]]

题意给定一个可重小写字符集合 $S$． Alice 初始时有空串 $A$，Bob 初始时有空串 $B$．两人轮流等概率取出集合 $S$ 中的一个字符 $c$，将它拼接到自己的字符串的后面，直至 $S$ 为空，每个字符只能被取一次，Alice 先手．如果最终 $A$ 的字典序严格大于 $B$，则 Alice 胜．求 Alice 胜的概率，答案对 $998244353$ 取模．

思路如果在某个字符 $i$，$A{i}>B{i}$，则已有 Alice 胜；若 $A{i}<B{i}$，则 Alice 败；否则 $A{i}=B{i}$，这个字符无法判断胜负，需要继续操作，我们称这种情形为平局．非平局时，两人互换结果，输赢翻转，概率相同，因此只需判断平局的概率．分为以下三种情形，式中 $p=\frac{\prod \operatorname{A}_{\text{字符}i\text{的总数}}^{\text{字符}i\text{的组数}}\times\text{组数}!}{\text{总数}!}$：

若每种字母的个数都是偶数：设 Alice 和 Bob 取得的字符串完全相同的概率为 $p$，则答案为 $\frac{1-p}{2}$．
若只有一种字母的个数是奇数：对于前 $\frac{n-1}{2}$ 个字符，设 Alice 和 Bob 取得的字符串完全相同的概率为 $p$，则答案为 $\frac{1-p}{2}+p=\frac{1+p}{2}$．
否则，答案为 $\frac{1}{2}$．

void eachT() {
    int n = read();

    int cnt[2] = { 0,0 };
    for (int i = 1; i <= n; i++) {
        char x; scanf("%c", &x);
        a[i] = read();
        cnt[a[i] & 1] += 1;   // 桶
    }

    // 第三种情形
    if (cnt[1] > 1) {
        printf("%lld\n", inv2);     // 1/2
        return;
    }

    // 计算 p(即代码中的 ans)
    ll ans = 1, ttcnt = 0;   // 总数
    for (int i = 1; i <= n; i++) {
        ans = ans * fac[a[i]] % MOD * facinv[a[i] / 2] % MOD;
        ttcnt += a[i];
    }
    ans = ans * facinv[ttcnt] % MOD * fac[ttcnt/2] % MOD;

    // 利用 p 计算答案
    // 第一种情形
    if (cnt[1] == 0) printf("%lld\n", (1 - ans + MOD) % MOD * inv2 % MOD);
    // 第二种情形
    else printf("%lld\n", (1 + ans + MOD) % MOD * inv2 % MOD);
}

CF921D. Good Trip (1900)

题意 $n$ 个人，$m$ 对朋友，第 $j$ 对朋友的友谊值为 $f_j~(1\leqslant j\leqslant m)$，进行 $k$ 次选择，每次等概率地选择俩人，如果选择的俩人是一对朋友，他们的友谊值将增加 $1$．求所有被选中的 $k$ 对的友谊值总和的期望值（在增加之前）．

思路易知分母是 $(C_n^2)^k$，它表示每次选择有 $C_n^2$ 种选择方式，共选择 $k$ 次，以下计算分子，分子是所有可能的选择方式的友谊值的总和．

因为只考虑友谊值的总和，它符合加法原理，所以可以按照朋友分开计算友谊值，再相加．

对于某对朋友，可能选择了 $0\sim k$ 次，如在 $k$ 次选择中选择 $i$ 次这对朋友，根据二项式定理，有 $C_k^i\cdot 1^i\cdot\big(C_n^2-1\big)^{k-i}$ 种选择方式，每种选择的友谊值总和为 $f+(f+1)+(f+2)+\dots+(f+i-1)=if+C_i^2$，因此所有情况的友谊值的总和为 $C_k^ip^{k-i}\big(if+C_i^2\big)$．（为了书写方便，这里记 $p=C_n^2$，下同）

将上式对 $i$ 求和，稍加化简，即

$\begin{align} S_j &=\sum_{i=0}^{k} C_k^i (p-1)^{k-i} \big(if+C_i^2\big) \\ &= \sum_{i=1}^{k} i C_k^i (p-1)^{k-i}f + \frac12\sum_{i=2}^{k} i(i-1) C_k^i (p-1)^{k-i} \\ &= \sum_{i=1}^{k} kC_{k-1}^{i-1} (p-1)^{k-i}f + \frac12\sum_{i=2}^{k} k(k-1)C_{k-2}^{i-2} (p-1)^{k-i} \\ &= kf\sum_{i=0}^{k-1} C_{k-1}^{i} (p-1)^{k-1-i} + \frac12k(k-1)\sum_{i=0}^{k-2} C_{k-2}^{i} (p-1)^{k-2-i} \\ &= kfp^{k-1} + \frac12k(k-1)p^{k-2}, \\ \end{align}$

熟知，$\sum\limits{i=0}^{k} C{k}^{i} p^{k-i} = (p+1)^{k}$．

由于有 $m$ 对朋友，对这些朋友求和，

$\begin{align} \sum_{j=1}^{m}S_j &=\sum_{j=1}^{m} \Big(kf_jp^{k-1} + \frac12k(k-1)p^{k-2} \Big) \\ &=kp^{k-1}\sum_{j=1}^{m}f_j + mC_k^2p^{k-2}, \\ \end{align}$

即是最终的分子．

答案即是

${\rm ans} = \frac{kp^{k-1}\sum_{j=1}^{m}f_j + mC_k^2p^{k-2}}{(C_n^2)^k}.$

核心部分：

ll n = read(), m = read(), k = read();
ll p = C2(n), ans = C2(k) * m * qpow(p, k - 2), sum = 0;
while (m--) {
    read(), read();   // 谁和谁是朋友不重要，只关心友谊值
    sum += read();
}
ans += k * sum * qpow(p, k - 1);
print(ans * qpow(qpow(p, k), MOD - 2));

时间复杂度 $\Theta(m+\log n)$，77ms．

评注数据范围较小，不化简也能过．

CF925G. One-Dimensional Puzzle (2000)

题意四种元素，按照 $1\to2,3,~2\to1,4,~3\to2,3,~4\to1,4$ 的顺序连接，求方法数。

思路 $1$ 和 $2$ 必须交替排列，在中间插入若干 $3$，$4$。注意到，将 $n$ 个物品放入 $m$ 个盒子，不能留空的方法数为 $C{n-1}^{m-1}$，允许不放的方法数为 $C{n+m-1}^{m-1}$。

int a = read(), b = read(), c = read(), d = read();
ll ans = 0;
if (a == 0 && b == 0) ans = (c == 0) ^ (d == 0) || (c == 0) && (d == 0);
else if (a == b) ans = C(a - 1 + c, c, p) * C(b + d, d, p) + C(a + c, c, p) * C(b - 1 + d, d, p);
else if (a == b + 1) ans = C(a - 1 + c, c, p) * C(b + d, d, p);
else if (b == a + 1) ans = C(a + c, c, p) * C(b - 1 + d, d, p);
printf("%lld\n", ans % p);

CF1922B. Forming Triangles (1200)

题意给出一些木棍，它们的长度是 $2^{a_i}$，问选择三根能构成三角形的方法数．

思路注意到 $\forall i<j<k,~2^i+2^j<2^k$，它们不能构成三角形，因此可能的情况只有等边三角形（C3(mp[i])）和腰比底长的等腰三角形（s[i-1] * C2(mp[i])）．

memset(mp, 0, sizeof mp);
int n = read();
ll ans = 0, s = 0;
for (int i = 1; i <= n; ++i) ++mp[read()];
for (int i = 0; i <= n; ++i) {
    ans += s * C2(mp[i]) + C3(mp[i]);
    s += mp[i];
}
printf("%lld\n", ans);

2022 ICPC 杭州 A. Modulo Ruins the Legend

题意给定 $a,b,s,m$，最小化 $(xa+yb+s) \bmod m$。([[../contests/2024-09-25：The 2022 ICPC Asia Hangzhou Regional Contest|2024-09-25：The 2022 ICPC Asia Hangzhou Regional Contest]])

思路根据裴蜀定理知存在 $x{0},y{0}$，使得 $x{0}a+y{0}b=d=(a,b)$，问题化为最小化 $(ud+s) \bmod m$，其中 $ud=xa+yb,\ x=ux{0},\ y=vy{0}$。

设答案为 $w\in[0,m)$，则 $ud+s+vm=w$，即 $ud+vm=w-s$，于是只能 $g=(m,d)\mid w-s$，因此取 $w=s \bmod g$。

解不定方程 $ud+vm=w-s$ 得到 $u,v$，再解不定方程 $ud=xa+yb$ 得到 $x,y$。

int n, m;
cin >> n >> m;
ll sum = 0;
for (int i = 0; i < n; i++) {
	int x;
	cin >> x;
	sum += x;
}
sum %= m;
ll a = n, b = n * (n + 1) / 2;
ll d = gcd(a, b), g = gcd(d, m);
ll ans = sum % g;
auto [k, t] = exexgcd(d, m, ans - sum);
auto [x, y] = exexgcd(a, b, d * k);
cout << ans << endl;
cout << (x % m + m) % m << " " << (y % m + m) % m << endl;