BZOJ 3823 定情信物：n 維立方體元素計數推導

問題描述

定義 0 維元素為點，1 維為線，2 維為面，3 維為體，以此類推。求 n 維立方體中各維元素個數，輸出所有維度個數的異或和模 p。

規律發現

令 f[i][j] 為 i 維立方體中 j 維元素個數。從 i-1 維擴展到 i 維時：
原有 j 維元素翻倍（兩側各一份）
原有 j-1 維元素各生成一個新 j 維元素（掃過形成）
遞推：f[i][j] = 2*f[i-1][j] + f[i-1][j-1]

閉式解推導

打表觀察發現：f[n][k] = 2^(n-k) * C(n, k)
驗證：n=3（立方體）：點 8=2^3·C(3,0)、線 12=2^2·C(3,1)、面 6=2^1·C(3,2)、體 1=2^0·C(3,3) ✓

線性計算異或和

由遞推關係：f[n][i] = f[n][i+1] * 2 * (i+1) / (n-i)
預處理模 p 逆元（線性篩法），從高維向低維遞推，累加異或。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
long long inv[MAXN];

int main() {
    int n, p; cin >> n >> p;
    // 線性求逆元
    inv[1] = 1;
    for (int i = 2; i <= n; ++i)
        inv[i] = (p - p/i) * inv[p%i] % p;
    long long ans = 1, cur = 1; // f[n][n] = 1
    for (int i = n-1; i >= 0; --i) {
        cur = cur * (i+1) % p * 2 % p * inv[n-i] % p; // f[n][i]
        ans ^= cur;
    }
    cout << ans << endl;
    return 0;
}

關鍵點

1. 組合幾何意義：n 維立方體有 2^n-k 個 k 維面（每個 k 維面由固定 n-k 個坐標決定，每個坐標 2 種選擇）
2. 線性逆元 O(n) 預處理，避免重複快速冪
3. 異或和而非求和，注意 ^= 操作

此題展示了從遞推關係到閉式解的數學推導能力，以及模算術中線性逆元的高效應用。