題目大意

用K$K$種顏色對一個n×m$n/times m$的矩形板染色。對于任意一條豎直的線，都能把矩形分成不為空的兩個部分（注意這里是分隔是沿著兩列的交界分隔），要求染色方案滿足每部分中的不同顏色種數要相同。 答案對109+7$10^9+7$取模。

1≤n≤1000,2≤m≤1000,1≤K≤106$1/le n/le1000,2/le m/le1000,1/le K/le10^6$

題目分析

這題剛開始看似乎無從下手，我們要找到一個比較好的突破口來做題。 考慮最左邊和最右邊兩列，它們具有一定的特殊性質。先考慮最左邊一列，可以發現除了最右邊一列，每一列的出現過的顏色都一定在第一列中出現過，這個可以使用反證法來證明：如果存在一種顏色是第一列沒有出現過的，并且假設其左邊的列都是第一列有的顏色，那么從這一列右邊切開，右邊部分的顏色種類數就是第一列的顏色種類數加一，然后我們從這一列左邊切開，可以發現右邊部分的顏色種類數顯然和左邊不一樣。 同理我們可以證明除了最左邊一列，每一列出現過的顏色都一定在最后一列出現過。的確，第一列和最后一列的顏色種類不一定完全相同，中間的列的顏色一定屬于這兩列顏色種類的交集。那么第一列和最后一列的顏色種類數是否相等呢？答案是肯定的。 那么正解就很顯然了，我們令fi,j$f_{i,j}$表示i$i$個格子填j$j$種顏色的方案數，枚舉a$a$為第一列的顏色種類數，b$b$為第一列和最后一列共有的顏色數，那么答案就是 ∑a∑b(K2a?b)(2a?bb)(2(a?b)a?b)(fn,aa!)2bn(m?2) $$/sum_a/sum_b{K/choose2a-b}{2a-b/choose b}{2(a-b)/choose a-b}/left(f_{n,a}a!/right)^2b^{n(m-2)}$$ 時間復雜度O(n2)$/mathrm O(n^2)$。

代碼實現