題解：十二重計數法

前置：

計數基礎（組合數，斯特林數）
多項式基礎（多項式 exp）

題面：

有 \(n\) 個球和 \(m\) 個盒子，要全部裝進盒子里。
還有一些限制條件，那么有多少種方法放球？（與放的先后順序無關）

限制條件分別如下：

\(\text{I}\)：球之間互不相同，盒子之間互不相同。
\(\text{II}\)：球之間互不相同，盒子之間互不相同，每個盒子至多裝一個球。
\(\text{III}\)：球之間互不相同，盒子之間互不相同，每個盒子至少裝一個球。

\(\text{IV}\)：球之間互不相同，盒子全部相同。
\(\text{V}\)：球之間互不相同，盒子全部相同，每個盒子至多裝一個球。
\(\text{VI}\)：球之間互不相同，盒子全部相同，每個盒子至少裝一個球。

\(\text{VII}\)：球全部相同，盒子之間互不相同。
\(\text{VIII}\)：球全部相同，盒子之間互不相同，每個盒子至多裝一個球。
\(\text{IX}\)：球全部相同，盒子之間互不相同，每個盒子至少裝一個球。

\(\text{X}\)：球全部相同，盒子全部相同。
\(\text{XI}\)：球全部相同，盒子全部相同，每個盒子至多裝一個球。
\(\text{XII}\)：球全部相同，盒子全部相同，每個盒子至少裝一個球。

\(\text{I}\)

容易發現是 \(m^n\)，每個球可以任意選。

\(\text{II}\)

枚舉哪些不放球，\(A_m^n\)。

\(\text{III}\)

因為非空，那么每一種方案每個盒子間都是本質不同的，所以其實就是斯特林數乘階乘，但是這里給出更為普遍一點的推法。

設 \(G_i\) 為欽定 \(i\) 個盒子可空方案數，\(F_i\) 為 \(i\) 個盒子不空方案數。

那么：

\[G_i=i^n \]

\[G_i=\sum_{j=0}^i{\binom{i}{j}F_j} \]

\[F_i=\sum_{j=0}^{i}{(-1)^{i-j}\binom{i}{j}G_j} \]

所以答案為：

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

\(\text{IV}\)

考慮枚舉多少個非空，因為盒子本質相同，所以不需要知道哪些為空。

剩下的盒子見 \(\text{VI}\)，所以答案就是 \(\sum_{i=0}^m{n \brace i}\)

\(\text{V}\)

發現交換兩個盒子的所有球是相同的方案，所以其實只有一種合法方案。

答案是：\([n\le m]\)

\(\text{VI}\)

這個其實就是將 \(n\) 個本質不同的數劃分為 \(m\) 個非空集合的方案數。

觀察 \(\text{III}\) 得知，在那個方案數統計中，每一個劃分方案都會被計算 \(m!\) 次，所以其實就得到了：

\[{n\brace m}=\sum_{i=0}^m{\frac{(-1)^{m-i}i^n}{i!(m-i)!}} \]

注意到 \(\text{IV}\) 需要求 \(n\brace i\)，那么考慮生成函數。

設 \(F_n=\sum_{i=0}^{+\infty}{{n \brace i}x^i}\)。

不過其實就只有 \(n+1\) 項有值。

由剛剛的推導得知：

\[F_n=\sum_{i=0}^{n}{\sum_{j=0}^i{\frac{(-1)^{i-j}j^n}{j!(i-j)!}}x^jx^{i-j}} \]

得到了一個卷積形式：

\[G_n=\sum_{i=0}^{n}{\frac{i^n}{i!}x^i} \]

\[H_n=\sum_{i=0}^{n}{\frac{(-1)^i}{i!}x^i} \]

\[F_n=G_n\times H_n \]

直接 NTT 即可。

\(\text{VII}\)

方案數只與每個盒子內的球數有關，直接插板法，先放 \(m\) 個球在每個里面，\(C_{n+m-1}^{m-1}\)。

\(\text{VIII}\)

枚舉哪些盒子是空的，\(C_{m}^{n}\)。

\(\text{IX}\)

更簡單的插板 \(C_{n-1}^{m-1}\)

\(\text{X}\)

假設方案數是 \(p_{n,m}\)，那么可以發現其實是在統計有多少種單調不降的序列，所有數的和是 \(n\)。

這樣一個序列一定是通過若干次前綴加構成的。

每次新加一個數考慮是否進行前綴加：

\[p_{i,j}=p_{i,j-1}+p_{i-j,j} \]

其實進行一些更為樸素的 \(dp\)，也可以推得，不過需要推的比較復雜。

但是這是 \(O(n^2)\) 的。

怎么優化呢？

首先現將轉移更改一下：

\[p_{i,j}=\sum_{k=0}{p_{i-kj,j-1}} \]

驚奇的發現如果設 \(P_{i}=\sum_{k=0}^{+\infty}{p_{k,i}x^k}\) 可以得到：

\[P_i=P_{i-1}\sum_{k=0}{x^{ik}} \]

那么：

\[P_m=\prod_{i=1}^{m}{(\sum_{k=0}{x^{ik}})}=\prod_{i=1}^m{\frac{1}{1-x^i}} \]

此時多項式求 \(\ln\) 再求 \(\exp\) 可得（\(\ln\) 只需手模泰勒展開或簡單求導積分即可）：

\[P_m=\exp \sum_{i=1}^m{\sum_{j=0}^{+\infty}{\frac{x^{ij}}{j}}} \]

\(\text{XI}\)

還是 \([n\le m]\)。

\(\text{XII}\)

先將 \(m\) 個球放進去，答案是 \(p_{n-m,m}\)。

代碼：

點擊查看代碼

const int N = 8e5 + 10, mod = 998244353;

#define int long long

#define emp emplace_back
#define pb push_back
#define fi first
#define se second

using pii = pair <int, int>;

int fac[N], inv[N], s[N], p[N], f[N], g[N];

int qpow(int x, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = res * x % mod;
        x = x * x % mod;
        b >>= 1;
    }
    return res;
}

int rev[N];
void NTT(int *a, int k, bool op = 0)
{
    for (int i = 0; i < k; i++) rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? k >> 1 : 0);
    for (int i = 0; i < k; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int len = 2; len <= k; len <<= 1)
    {
        int wn = qpow(3, (mod - 1) / len);
        for (int l = 0, mid = (len >> 1) - 1; l + len - 1 < k; l += len, mid += len)
        {
            int w = 1;
            for (int i = l; i <= mid; i++, w = w * wn % mod)
            {
                int x = a[i], y = a[i + (len >> 1)] * w % mod;
                a[i] = x + y;
                if (a[i] >= mod) a[i] -= mod;
                a[i + (len >> 1)] = x - y;
                if (a[i + (len >> 1)] < 0) a[i + (len >> 1)] += mod;
            }
        }
    }
    if (op)
    {
        reverse(a + 1, a + k);
        int inv = qpow(k, mod - 2);
        for (int i = 0; i < k; i++) a[i] = a[i] * inv % mod;
    }
}

void fill(int *f, int l, int r, int v) {for (int i = l; i < r; i++) f[i] = v;}

void copy(int *f, int *h, int l, int r) {for (int i = l; i < r; i++) h[i] = f[i];}

int mulf[N], mulg[N];
void mul(int *f, int *g, int *h, int n, int m)
{
    int len = 1;
    while (len < n + m) len <<= 1;
    fill(mulf, 0, len, 0), fill(mulg, 0, len, 0);
    copy(f, mulf, 0, len), copy(g, mulg, 0, len);
    NTT(mulf, len, 0), NTT(mulg, len, 0);
    for (int i = 0; i < len; i++) h[i] = mulf[i] * mulg[i] % mod;
    NTT(h, len, 1);
    for (int i = n + m - 1; i < len; i++) h[i] = 0;
}

int invh[N], invf[N];

void Inv(int *f, int *h, int n)
{
    if (n == 1) return h[0] = qpow(f[0], mod - 2), void();
    Inv(f, h, (n + 1) >> 1);
    int len = 1;
    while (len < 2 * n) len <<= 1;
    fill(invf, 0, len, 0);
    copy(f, invf, 0, n);
    NTT(invf, len, 0), NTT(h, len, 0);
    for (int i = 0; i < len; i++) h[i] = h[i] * (2 - h[i] * invf[i] % mod + mod) % mod;
    NTT(h, len, 1);
    fill(h, n, len, 0);
}

void dev(int *f, int len) {for (int i = 1; i < len; i++) f[i - 1] = i * f[i] % mod; f[len - 1] = 0;}
void redev(int *f, int len) {for (int i = len - 1; i >= 0; i--) f[i + 1] = f[i] * qpow(i + 1, mod - 2) % mod; f[0] = 0;}

int lnf[N], lng[N];

void ln(int *f, int *h, int n)
{
    fill(lnf, 0, 2 * n, 0), fill(lng, 0, 2 * n, 0);
    copy(f, lnf, 0, n);
    dev(lnf, n);
    Inv(f, lng, n);
    mul(lnf, lng, h, n, n);
    redev(h, n);
    fill(h, n, 2 * n, 0);
}

int _expf[N], expg[N];

void exp(int *f, int *h, int n)
{
    if (n == 1) return h[0] = 1, void();
    exp(f, h, (n + 1) >> 1);
    fill(_expf, 0, 2 * n, 0);
    fill(expg, 0, 2 * n, 0);
    copy(h, _expf, 0, n);
    fill(_expf, n, 2 * n, 0);
    ln(_expf, expg, n);
    for (int i = 0; i < n; i++) expg[i] = (-expg[i] + f[i] + mod) % mod;
    expg[0]++;
    mul(_expf, expg, h, n, n);
    fill(h, n, 2 * n, 0);
}

// #pragma region count

int C(int n, int m) {return n >= m ? fac[n] * inv[m] % mod * inv[n - m] % mod : 0;}

int A(int n, int m) {return C(n, m) * fac[m] % mod;}

int I(int n, int m) {return qpow(m, n);}

int II(int n, int m) {return A(m, n);}

int III(int n, int m)
{
    int flag = m & 1 ? -1 : 1, ans = 0;
    for (int i = 0; i <= m; i++) ans = (ans + flag * qpow(i, n) % mod * C(m, i) % mod + mod) % mod, flag = -flag;
    return ans;
}

int IV(int n, int m)
{
    int ans = 0;
    for (int i = 0; i <= m; i++) ans = (ans + s[m - i]) % mod;
    return ans;
}

int V(int n, int m) {return n <= m;}

int VI(int n, int m) {return s[m];}

int VII(int n, int m) {return C(n + m - 1, m - 1);}

int VIII(int n, int m) {return C(m, n);}

int IX(int n, int m) {return C(n - 1, m - 1);}

int X(int n, int m) {return p[n];}

int XI(int n, int m) {return n <= m;}

int XII(int n, int m) {return p[n - m];}

// #pragma endregion

signed main()
{
    // freopen("data.in", "r", stdin); freopen("data.out", "w", stdout);
    // freopen("mission.in", "r", stdin); freopen("mission.out", "w", stdout);
    ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int n, m; cin >> n >> m;
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= n + m; i++) fac[i] = fac[i - 1] * i % mod, inv[i] = qpow(fac[i], mod - 2);
    for (int i = 0; i <= n; i++) f[i] = qpow(i, n) * inv[i] % mod;
    for (int i = 0; i <= n; i++) g[i] = (i & 1 ? mod - 1 : 1) * inv[i] % mod;
    mul(f, g, s, n + 1, n + 1);
    fill(s, n + 1, N, 0);
    fill(f, 0, N, 0);
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; i * j <= n; j++)
        {
            (f[i * j] += qpow(j, mod - 2)) %= mod;
        }
    }
    exp(f, p, n + 1);
    cout << I(n, m) << '\n';
    cout << II(n, m) << '\n';
    cout << III(n, m) << '\n';
    cout << IV(n, m) << '\n';
    cout << V(n, m) << '\n';
    cout << VI(n, m) << '\n';
    cout << VII(n, m) << '\n';
    cout << VIII(n, m) << '\n';
    cout << IX(n, m) << '\n';
    cout << X(n, m) << '\n';
    cout << XI(n, m) << '\n';
    cout << XII(n, m) << '\n';

    return 0;
}

posted @ 2025-10-26 12:11 QEDQEDQED 閱讀(42) 評論(6) 收藏舉報

刷新頁面返回頂部

QEDQEDQED

題解：十二重計數法

題解：十二重計數法

\(\text{I}\)

\(\text{II}\)

\(\text{III}\)

\(\text{IV}\)

\(\text{V}\)

\(\text{VI}\)

\(\text{VII}\)

\(\text{VIII}\)

\(\text{IX}\)

\(\text{X}\)

\(\text{XI}\)

\(\text{XII}\)

公告