CF1228E Another Filling the Grid 题解

tag: 容斥原题 + 组合数

设 F [ i ] F[i] F[i] 表示至少 i i i 行不合法的方案数。

F i = ( k n − i × ( k − 1 ) i − ( k − 1 ) n ) n F_i = (k^{n - i} \times (k - 1)^i - (k - 1)^n)^n Fi​=(kn−i×(k−1)i−(k−1)n)n。

根据容斥原理我们可以知道答案就是： ∑ i = 0 n ( − 1 ) i × C ( n , i ) × F i \sum_{i = 0}^n (-1)^i \times C(n, i) \times F_i ∑i=0n​(−1)i×C(n,i)×Fi​。

时间复杂度： O ( n log ⁡ n ) O(n \log n) O(nlogn)。