BZOJ 2339：HNOI 2011 卡農 - 組合數學計數

問題描述

從 {1,2,...,n} 中選取 m 個集合（可重複選擇元素，集合間有序），要求每個數字 1..n 在所有集合中總共出現 偶數次。求方案數模 100000007。

數學推導

令 f(m) 為答案。考慮指數生成函數或容斥。標準結論：

f(m) = (1/2^n) * Σ_{k=0..n} C(n,k) * (n - 2k)^m （模素數下用逆元）。

但 n,m ≤ 10^6 需 O(m) 或 O(n) 算法。遞推公式：

設 A_i = (2^n - 1 - i + 1) = (2^n - i)。則 f(m) = (1/m!) * Σ ... 具體遞推見代碼。

代碼實現 (基於遞推)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 100000007;
const int MAXM = 1000005;

long long mod_pow(long long a, long long e) {
    long long r = 1;
    while (e) { if (e&1) r=r*a%MOD; a=a*a%MOD; e>>=1; }
    return r;
}

int main() {
    int n, m; scanf("%d%d", &n, &m);
    long long cnt = (mod_pow(2, n) - 1 + MOD) % MOD; // 2^n - 1
    vector A(m+1), f(m+1);
    A[1] = cnt;
    for (int i = 2; i <= m; ++i) A[i] = A[i-1] * (cnt - i + 2) % MOD; // 下降階乘

    f[1] = f[2] = 0;
    for (int i = 3; i <= m; ++i) {
        f[i] = (A[i-1] - f[i-1] - f[i-2] * (i-1) % MOD * (cnt - i + 2) % MOD + 2*MOD) % MOD;
    }

    long long fact = 1;
    for (int i = 1; i <= m; ++i) fact = fact * i % MOD;
    long long ans = f[m] * mod_pow(fact, MOD-2) % MOD;
    printf("%lld\n", ans);
    return 0;
}

關鍵公式來源

此為組合數學經典問題「偶數次出現的集合族計數」，可通過指數生成函數 (cosh x)^n 展開或容斥原理導出遞推。代碼中的遞推為已化簡形式。

總結

高階組合計數題，需熟悉生成函數、容斥、模逆元等工具。比賽中通常需查閱結論或預先掌握相關恒等式。