这道题实际上数学家很早以前就有研究，有一个东西叫做“Poly-Bernoulli Numbers"专门就是研究这个东西的。先把公式亮出来吧。
或
其中，\({n\brace m}\) 是第二类斯特林数。\(B_n^{(-k)}\) 代表 \(n\) 行 \(k\) 列的合法矩阵的个数。这篇博客主要来讲一下第一个公式的组合意义。
首先有一个非常重要的结论，就是在合法的矩阵中，一定不会出现 \(\begin{pmatrix} 01\\10\end{pmatrix}\) 和 \(\begin{pmatrix}10\\01\end{pmatrix}\) 这样的子矩阵。因为一旦出现这样的子矩阵，我们只需要将0变成1，将1变成0，那么得到的就是一个与原矩阵不同的，但是存在1的个数相同行/列的另一个矩阵。我们把这样子矩阵叫做“小禁止”。
好的，有了这个矩阵之后，我们来看一下一些定义。
定义 列的字符集
我们把可以在一个矩阵中共存的列的集合叫列的字符集。
注意，在这条定义中，我们把一列看成是一个字母，如果一些字母可以合法地共存于最终的矩阵中，就把这些字母归为一个列的字符集。当然，列的字符集可以有很多种。
为了方便起见，我们将字符集中全1的字母和全0的字母全扔掉。现在来考虑大小为 \(m-1\) 的字符集有多少种。
现在，我们把这个字符集按照字母中含有1的个数从小到大排序。严谨起见，我们来思考这样一个问题，如果我把每一行具有多少个1告诉你，请问这个字符集是不是唯一确定的？
答案是肯定的。根据我们已经说过的结论，要想让这个字符集中不出现 \(\begin{pmatrix}01\\10\end{pmatrix}\)，那么对于某一行的所有1，它们必须全部靠后站。
举个例子。比如我告诉你第一行有0个1，第二行有1个1，第三行有1个1，第四行有2个1，第五行有1个1。那么你的字符集必须长成这样：\(\begin{pmatrix}00\\01\\01\\11\\01\end{pmatrix}\)，而不能长成这样：\(\begin{pmatrix}00\\10\\01\\11\\01\end{pmatrix}\)。这两个字符集都已经排序，而且没有全0的列和全1的列，但是由于第二个矩阵中出现了“小禁止”，所以被叉掉了。
由于我们已经把全1的字母和全0的字母都扔掉了。所以每行的1的个数的范围一定在 \([0,m-1]\) 中。而且一定会取遍0到m之间的所有整数。因为如果中间漏了一个整数，就一定会存在1的数量相同的列。所以，我们现在的任务就是将 \(1\sim n\) 这 \(n\) 行放进带有标号的 \(m\) 个盒子中，对应着 \({n\brace m}m!\)。
现在，我们再将全0的列和全1的列加到我们的字符集中，并尝试用这 \(m+1\) 个字符去填充 \(k\) 列。方案数 \((m+1)^k\)。
最后那个 \((-1)^{n+m}\) 就是容斥系数了。这是因为我们并没有规定这 \(m+1\) 个字符都必须出现在这 \(k\) 中，所以不同的字符集可能会产生相同的填充方法，所以需要容斥。
至于第二个公式，感兴趣的同学可以参考论文。http://math.colgate.edu/~integers/i2/i2.pdf
//由于我不会FFT，这个代码只能拿到99分。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define FILEIN(s) freopen(s".in", "r", stdin);
#define FILEOUT(s) freopen(s".out", "w", stdout)
#define mem(s, v) memset(s, v, sizeof s)
inline int read(void) {
int x = 0, f = 1; char ch = getchar();
while (ch < ‘0‘ || ch > ‘9‘) { if (ch == ‘-‘) f = -1; ch = getchar(); }
while (ch >= ‘0‘ && ch <= ‘9‘) { x = x * 10 + ch - ‘0‘; ch = getchar(); }
return f * x;
}
const int mod = 998244353, maxn = 5005;
int n, m;
long long S[maxn][maxn], factor[maxn];
long long ans;
long long power(long long a, long long b) {
long long res = 1;
for (; b; b >>= 1) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
}
return res;
}
void prework(void) {
S[0][0] = 1;
factor[0] = 1;
for (int i = 1; i <= n; ++ i) {
factor[i] = factor[i - 1] * i % mod;
S[i][0] = 0;
for (int j = 1; j <= i; ++ j)
S[i][j] = (S[i - 1][j - 1] + S[i - 1][j] * j % mod) % mod;
}
}
int main() {
FILEIN("W2B"); FILEOUT("W2B");
n = read(); m = read();
prework();
for (int k = 0; k <= n; ++ k) {
long long sum = factor[k] * S[n][k] % mod * power(k + 1, m) % mod;
if ((k + n) & 1) (ans -= sum) %= mod;
else (ans += sum) %= mod;
}
if (ans < 0) ans += mod;
printf("%lld\n", ans);
return 0;
}
原文：https://www.cnblogs.com/little-aztl/p/14882576.html