\(f(i)\)：满足 \(n\) 行 \(m\) 列每行每列都有颜色，最多用了 \(j\) 种颜色的方案数
根据容斥原理
\[ f(i)=[(i+1)^m-1]^n-\sum_{i=1}^m(-1)^{k-1}C_m^k[(i+1)^{m-k}-1]^n \]意思是对于每一行，每个格子都可以填 \(i\) 种颜色或不填；但是整行不能一个格子都不填色，所以减一；而有 \(n\) 行，故为 \([(i+1)^m-1]^n\)
但是可能存在一列没有格子填色，所以容斥处理：枚举 \(k\) 列没有格子填色，同理方案数为 \([(i+1)^{m-k}-1]^n\)，共 \(m\) 列，所以有系数 \(C_m^k\)
答案可以容斥解释，但是用二项式反演更不费脑子，何况各种反演本质上都是容斥：
用 最多 \(c\) 种颜色的方案数 算 恰好 \(c\) 种颜色的方案数，这不就是二项式反演；令 \(g(i)\) 为恰好 \(i\) 种颜色的方案数，显然
\[ f(i)=\sum_{k=1}^iC_i^kg(k) \]故
\[ g(i)=\sum_{k=1}^i(-1)^{i-k}C_i^kf(k) \] 标签：种颜色,格子,反演,题解,sum,容斥,问题,填色,染色 From： https://www.cnblogs.com/laijinyi/p/18148374