题解里大部分做法要做两次二项式反演，不知为何有点喜感
老规矩，先说我的做法：
方法1：
我一开始也想到了要做两次二项式反演，但感觉好麻烦，于是把一个二项式反演换成了\(dp\)，复杂度就差了一些
首先我们发现行列的限制不好容斥，因此我们考虑容斥颜色的限制。具体的，设\(f_i\)表示有至少\(i\)个颜色不选的方案数，\(g_i\)表示恰好有\(i\)个颜色不选的方案数。可以得到\(g_i = \sum_{j=i}^{n}{(-1)^{j-i}\binom{j}{i}f_j}\)，于是我们考虑怎么求\(f_i\)
我们考虑一个比较朴素的\(dp\)，设\(dp_{i,j,k}\)表示前\(i\)行染了\(j\)列，能染\(k\)种颜色的方案数
可以得到递推式：
其中\(\sum_{l=0}^{j}{\binom{j}{l} k^l}\)表示染过的列也可以再染的方案数；\(\sum_{l=0}^{m-j}{\binom{m-j}{l} k^l dp_{i-1,j-l}}\)则表示这一行中选一些没染的列染掉的方案数
于是我们考虑怎么优化：
首先前面\(\sum_{l=0}^{j}{\binom{j}{l} k^l}\)这部分可以预处理掉，我们不妨设\(s_{i,j} = \sum_{l=0}^{i}{\binom{i}{l} j^l}\)
然后我们推一下\(dp_{i,j-1,k}\)，看两个式子有没有什么共同点
好吧，推着推着突然发现自己推不下去了，还是直接说结果把：
于是我们就可以\(O(nmc)\)的得到\(dp\)答案，\(f_i = dp_{n,m,c-i}\)，最终复杂度\(O(n^3)\)
方法2：
首先我们处理颜色全部使用的限制：设\(f_i\)表示只用了\(i\)中颜色，并且满足行和列染色限制的方案数，可以得到：
然后我们考虑怎么计算\(f_i\)。我们固定每一行都要染色，选其中的\(k\)列随便染色，然后用二项式反演容斥计算：
其中\((i+1)^k-1\)表示固定的这\(k\)列随便染，而\(-1\)是减掉全为空的情况。最终复杂度\(O(c \log n)\)