Description：

给出一个 $n\times m$ 大小的矩形，每个位置可以填上 $[1,c]$ 中的任意一个数，要求填好后任意两行互不等价且任意两列互不等价，两行或两列等价当且仅当对应位置完全相同，求方案数 。

$n,m\leqslant 5000$

Solution：

首先如果不考虑列， $n\times m$ 的方阵行不等价的方案数为 $(c^m)^\underline n$ 。

设 $g(m)$ 表示行不等价的情况下， $m$ 列的矩形的方案数， $g(m)=(c^m)^{\underline n}$ 。

$f(m)$ 表示行和列都不等价的情况下 $m$ 列的矩形的方案数，枚举有哪些列是等价的： $$ g(m)=\sum_{i=1}^m\begin{Bmatrix}m\\i\end{Bmatrix}f(i) $$ 反演一下： $$ f(m)=\sum_{i=1}^m(-1)^{m-i}\begin{bmatrix}m\\i\end{bmatrix}g(i) $$ 于是就可以 $O(n^2)$ 计算了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXN 5010

int n,m,c;

#define MOD 1004535809

int S[MAXN][MAXN];

int power[MAXN];

int g[MAXN];

int main()

{

	scanf("%d%d%d",&n,&m,&c);

	S[0][0] = 1;power[0] = 1;

	for(int i = 1;i <= m;++i)

	{

		S[i][0] = 0;

		for(int j = 1;j <= i;++j)

			S[i][j] = (S[i - 1][j - 1] + 1ll * S[i - 1][j] * (i - 1) % MOD) % MOD;

	}

	for(int i = 1;i <= m;++i)

	{

		power[i] = 1ll * power[i - 1] * c % MOD;

		g[i] = 1;

		for(int cur = power[i],j = 1;j <= n && cur >= 0;++j,--cur)g[i] = 1ll * g[i] * cur % MOD;

	}

	int ans = 0;

	for(int i = 1;i <= m;++i)

	{

		ans = (ans + 1ll * (((m - i) & 1) ? MOD - 1 : 1) * S[m][i] % MOD * g[i] % MOD) % MOD;

	}

	cout << ans << endl;

	return 0;

}