题解 P5824 【十二重计数法】

CYJian · 2020-01-13 11:56:59 · 题解

#### 一、球不同，盒子不同，无其他限制显然为 $m^n

二、球不同，盒子不同，每个盒子至多装一个球

考虑相当于每个球找一个没有被选过的盒子放进去。不难发现，方案数为 m^{\underline{n}}

三、球不同，盒子不同，每个盒子至少装一个球

考虑容斥：枚举多少个盒子空了，然后剩下的部分就是第一个部分了。然后就可以得到下面这个式子：

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

四、球不同，盒子相同，无其他限制

考虑第二类斯特林数： S_{n,m} 表示 n 个不同的元素组成 m 个非空集合的方案数。

考虑枚举多少个盒子里头装了球，那么答案为：

\sum_{i=1}^{m} S_{n,i}

蒯第二类斯特林数 · 行就行了

五、球不同，盒子相同，每个盒子至多装一个球

~~最思博的部分了~~不论放到哪个盒子里头都是一样的，所以答案就是 [n \leq m]

六、球不同，盒子相同，每个盒子至少装一个球

根据第二类斯特林数的定义，显然答案为 S_{n,m}

七、球相同，盒子不相同，无其他限制

利用插板法，我们可以知道，答案为 \binom{n+m-1}{m-1}

八、球相同，盒子不相同，每个盒子至多装一个球

盒子不同，我们相当于要选出 n 个盒子装球，剩下 m-n 个盒子不装球。

所以答案就是 \binom{m}{n}

九、球相同，盒子不相同，每个盒子至少装一个球

同样利用插板法，我们先钦定每个盒子里头放一个球，剩下 n-m 个球按照第七个做就行了。

答案即为 \binom{n-1}{m-1}

十、球相同，盒子相同，无其他限制

设 p_{n,m} 表示“划分数”——即将 n 划分成 m 个自然数的可重集的方案数。那么我们要的答案就是 p_{n,m}

这个东西有一个非常经典的时空复杂度为 O(n^2) 的 dp：

p_{i,j} = p_{i-j,j} + p_{i,j-1}

两者的意思分别为：将 j 个自然数同时 +1、加入一个 0 到可重集中。

不难发现这样的确可以不重不漏地计数。

再考虑优化：我们构造一个多项式为：

F_i(x)=p_{0,i}+p_{1,i}x+p_{2,i}x^{2}+p_{3,i}x^{3} \dots

那么根据上面的转移，我们有：

F_i(x) = F_{i-1}(x) \times (1+x^i+x^{2i}+x^{3i}\dots)

F_i(x) = \frac{F_{i-1}(x)}{1-x^{i}}

那么也就不难得到：

F_{i}(x) = \prod_{j=1}^{i} \frac{1}{1-x^{j}}

这个东西和付公主的背包是一样的。具体做法就是求 \ln ，加起来再 \exp 回去，最后求个逆就完了。

考虑这个东西如何快速求 \ln：

G(x) = \ln (1-x^{i})

G'(x) = \frac{-ix^{i-1}}{1-x^{i}}

G'(x) = (-ix^{i-1}) \times \frac{1}{1-x^{i}}

G'(x) = (-ix^{i-1}) \times \sum_{j=0}^{\infty} x^{ij}

G'(x) = -\sum_{j=1}^{\infty} ix^{ij-1}

G(x) = -\sum_{j=1}^{\infty} \frac{x^{ij}}{j}

然后在模 x^{n+1} 意义下做这个东西就完事了。

十一、球相同，盒子相同，每个盒子至多装一个球

和第五个是一样的东西，就是 [n\leq m]。

十二、球相同，盒子相同，每个盒子至少装一个球

考虑就是将上面的“划分数”中的自然数变成正整数，我们强制现在每个盒子里头放一个球，就是同样的问题了。答案即为 p_{n-m,m}。

完整代码比较长，这里略去多项式板子以及基础数论部分的代码（因为用的是 vim，所以可能有很多折叠标记）

/********************************************************************************

    Code by a weak man who named CYJian, and he hopes the code can get more scores.

    Algorithm: 

 ********************************************************************************/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

//{{{ FAST IO
const int __SIZE = 1 << 18;
char ibuf[__SIZE], *iS, *iT;

#define ge (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
#define ri read_int()
#define rl read_ll()
#define FILE(s) freopen(s"in", "r", stdin), freopen(s"out", "w", stdout)

template<typename T>
inline void read(T &x) {
    char ch, t = 0; x = 0;
    while(!isdigit(ch = ge)) t |= ch == '-';
    while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
    x = t ? -x : x;
}
inline int read_int() { int x; return read(x), x; }
inline ll read_ll() { ll x; return read(x), x; }
//}}}

template<typename T> inline void chkmin(T&a, T b) { a = a < b ? a : b; }
template<typename T> inline void chkmax(T&a, T b) { a = a > b ? a : b; }

const int MAXN = 530010;
const int mod = 998244353;

inline int Mod(int x) { return x >= mod ? x - mod : x; }
inline void Add(int &x, int y) { x += y, x -= x >= mod ? mod : 0; }

int n, m;

int fac[MAXN];
int inv[MAXN];
int ifac[MAXN];

int tN;
int N, InvN;
int p[MAXN];
int G[MAXN];
int S[MAXN];
int F[MAXN];

int A[MAXN];
int B[MAXN];
int tA[MAXN];
int tB[MAXN];
int tC[MAXN];
int tD[MAXN];

//{{{ Math And Prework
inline int fsp(int x, int k = mod - 2) {}// 快速幂
inline int C(int n, int m) {} // 组合数
inline void Combine_init(int n) {} // 预处理阶乘以及逆元
inline void Prework() {} // 预处理原根
inline void NTT_init(int n) {}
inline void NTT(int a[], int k) {} // 快速数论变换
inline void GetInv(int A[], int B[], int n) {} // 多项式求逆
inline void GetLn(int A[], int B[], int n) {} // 多项式求对数
inline void GetExp(int A[], int B[], int n) {} // 多项式 exp

inline void init(int n, int m) {
    Prework(), Combine_init(n + m), NTT_init(max(n, m));

    for(int i = 0; i <= n; i++) {
        A[i] = i & 1 ? mod - ifac[i] : ifac[i];
        B[i] = 1LL * fsp(i, n) * ifac[i] % mod;
    } NTT(A, 1), NTT(B, 1);
    for(int i = 0; i < N; i++) A[i] = 1LL * A[i] * B[i] % mod;
    NTT(A, -1);
    for(int i = 0; i <= n; i++) S[i] = A[i]; // 第二类斯特林数

    memset(A, 0, sizeof(A));
    for(int i = 1; i <= m; i++)
        for(int j = i; j <= n; j += i)
            Add(A[j], mod - inv[j / i]);
    memset(B, 0, sizeof(B)), GetExp(A, B, n + 1);
    memset(A, 0, sizeof(A)), GetInv(B, A, n + 1);
    for(int i = 0; i <= n; i++) F[i] = A[i]; // p_{i, m}
}
//}}}

//{{{ solve01
inline int solve01() { return fsp(m, n); }
//}}}

//{{{ solve02
inline int solve02() {
    int res = 1;
    for(int i = 0; i < n; i++)
        res = 1LL * res * (m - i) % mod;
    return res;
}
//}}}

//{{{ solve03
inline int solve03() {
    int res = 0;
    for(int i = 0; i < m; i++)
        res = (res + 1LL * (i & 1 ? mod - C(m, i) : C(m, i)) * fsp(m - i, n)) % mod;
    return res;
}
//}}}

//{{{ solve04
inline int solve04() {
    int res = 0;
    for(int i = 1; i <= m; i++) Add(res, S[i]);
    return res;
}
//}}}

//{{{ solve05
inline int solve05() { return n <= m; }
//}}}

//{{{ solve06
inline int solve06() { return S[m]; }
//}}}

//{{{ solve07
inline int solve07() { return C(n + m - 1, m - 1); }
//}}}

//{{{ solve08
inline int solve08() { return C(m, n); }
//}}}

//{{{ solve09
inline int solve09() { return C(n - 1, m - 1); }
//}}}

//{{{ solve10
inline int solve10() { return F[n]; }
//}}}

//{{{ solve11
inline int solve11() { return n <= m; }
//}}}

//{{{ solve12
inline int solve12() { return n >= m ? F[n - m] : 0; }
//}}}

int main() {
#ifdef LOCAL
    FILE("");
#endif
    n = ri, m = ri, init(n, m);
    cout << solve01() << endl;
    cout << solve02() << endl;
    cout << solve03() << endl;
    cout << solve04() << endl;
    cout << solve05() << endl;
    cout << solve06() << endl;
    cout << solve07() << endl;
    cout << solve08() << endl;
    cout << solve09() << endl;
    cout << solve10() << endl;
    cout << solve11() << endl;
    cout << solve12() << endl;
    return 0;
}