给出一个 (n imes m) 的矩阵，每个位置可以填上 ([1,c]) 中的任意整数。
要求填好后任意两行互不等价，且任意两列互不等价。两行或两列等价当且仅当对应位置完全相同，求方案数。
(n,mleq 4000)
一道斯特林反演题。
直接考虑不好考虑，所以先只考虑行，设 (f_m) 表示只考虑行互不等价，矩阵 (n imes m) 的方案数。
一共有 (c^m) 种互不等价的方案，那么 (f_m=(c^m)^{underline{n}}) 。
然后设 (g_m) 表示行和列都不等价，矩阵 (n imes m) 的方案数，那么就有：
[f_m=sum_{i=1}^megin{Bmatrix}m\iend{Bmatrix}g_i
]
具体的就是先分成 (i) 个互不等价的集合，然后分配 (m) 列。
斯特林反演之后就有：
[g_m=sum_{i=1}^megin{bmatrix}m\iend{bmatrix}(-1)^{m-i}f_i
]
然后就做完了。
Code（topcoder的阴间提交方式）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 4e3;
const int p = 1e9 + 7;
using namespace std;
int S[N + 1][N + 1],f[N + 1];
int mypow(int a,int x){int s = 1;for (;x;x & 1 ? s = 1ll * s * a % p : 0,a = 1ll * a * a % p,x >>= 1);return s;}
void prework(int m)
{
memset(S,0,sizeof(S));
S[0][0] = 1;
for (int i = 1;i <= m;i++)
for (int j = 1;j <= i;j++)
S[i][j] = (S[i - 1][j - 1] + 1ll * (i - 1) * S[i - 1][j] % p) % p;
}
class CountTables
{
public :
int howMany(int n,int m,int c)
{
prework(m);
int ans = 0;
for (int i = 1;i <= m;i++)
{
int now = mypow(c,i);
f[i] = 1;
for (int j = 1;j <= n;j++)
f[i] = 1ll * f[i] * (now - j + 1) % p;
}
for (int i = 1;i <= m;i++)
ans += 1ll * S[m][i] * ((m - i) % 2 == 0 ? 1 : -1) * f[i] % p,ans %= p;
return (ans + p) % p;
}
};