Gym 101194H 2016 EC-Final H題

題意

  給一個 n ∗ m n*m n∗m 的格子矩陣，現在要在這些格子裡面填數，填的數字是 [ 1 , k ] [1,k] [1,k] 中的整數，每個數可以填多次。定義好格子：一個格子所在的行和列中的每個格子中的數都嚴格小于該格子中的數。假設 A g A_g Ag​ 為矩陣中好格子數量為 g g g 時填數的方案數，現在要輸出 ∑ g = 0 n ∗ m ( g + 1 ) A g \sum_{g=0}^{n*m}(g+1)A_g ∑g=0n∗m​(g+1)Ag​

分析

  首先我們将輸入出的表達式拆分開得到 ∑ g = 0 n ∗ m g A g + ∑ g = 0 n ∗ m A g \sum_{g=0}^{n*m}gA_g+\sum_{g=0}^{n*m}A_g ∑g=0n∗m​gAg​+∑g=0n∗m​Ag​ ，回顧一下 A g A_g Ag​ 表示的是矩陣中有 g g g 個好格子的方案數。然後我們先看兩個加數後面的那個部分表示的含義，直覺上看這個和包括不存在好格子時的方案數；隻有一個好格子時的方案數；有 n ∗ m n*m n∗m 個好格子時的方案數等。這樣的話無論怎麼填數，其結果都是上述情況中的一種。那麼很顯然這一部分的方案數應該是 K n ∗ m K^{n*m} Kn∗m. 下面我們再看看前面這一部分，跟後面不一樣的是這裡所求的和的每一項都帶了一個系數 g g g 表示有 g g g 個好格子時的方案數應該乘以該系數。這樣我們不好直接找通項求和，那麼我們現在換個思路求。我們将重心放到 n ∗ m n*m n∗m 個格子上，而不是原來的 g g g 上。意思就是我們看當第 x x x 行，第 y y y 列的這個格子是好格子的時候，他能填數的方案數時多少，再看看他對整個結果的貢獻是多少。兩者相乘，就可以作為答案的一部分。

  這裡強調一下，因為看的是每個格子的貢獻，是以隻要貢獻算對了是不會有重複的。

  下面這塊有一個轉化，舉個例子說明。當隻有一個格子是好格子的時候，按原來整體的思想答案應該是 A 1 A_1 A1​；假設格子1 ( x 1 , y 1 ) (x_1,y_1) (x1​,y1​) 和格子2 ( x 2 , y 2 ) (x_2,y_2) (x2​,y2​) 有且僅有這兩塊格子是好格子，很顯然他們不可能在同一行或者同一列。那麼當我們用原來的整體思想來看的話應該，此時的答案應該是 2 ∗ A 2 2*A_2 2∗A2​ 這時候我們可以将這兩份 A 2 A_2 A2​ 同時分給 格子1和格子2。再看如果隻有三個好格子的情況，同樣的原來的答案是 3 ∗ A 3 3*A_3 3∗A3​, 我們可以把這三個分給那三個好格子。以此類推，對于每個格子 ( x , y ) (x,y) (x,y) 他的貢獻應當是 ∑ i = 1 m ∗ n A g \sum^{m*n}_{i=1}A_g ∑i=1m∗n​Ag​ 。

  這樣我們我們會發現，如果 i i i 從0開始那麼就是随便亂擺，但是這裡是從1開始的，那麼我們應當保證至少有一個格子是好格子，其他的就可以随便亂擺了，分析和上面 i i i 從0開始是一樣的，這裡就不細說了。現在我們來看好格子和與之同行同列的格子填數的種類，首先好格子至少必須填 2 2 2，其他的全填 1 1 1；好格子的填數範圍是 [ 1 , k ] [1,k] [1,k] ，其他的隻要比這個數小就行了，一共有 m − 1 + n − 1 m-1+n-1 m−1+n−1 個數，每個數可以是 [ 1 , i − 1 ] [1,i-1] [1,i−1]( i i i是好格子的填的數)一共 i − 1 i-1 i−1個數 。那麼這一塊的種類數就是 ∑ i = 2 k ( i − 1 ) m − 1 + n − 1 \sum_{i=2}^{k}(i-1)^{m-1+n-1} ∑i=2k​(i−1)m−1+n−1。然後剩下的數就是随便亂填了，剩餘 ( n − 1 ) ∗ ( m − 1 ) (n-1)*(m-1) (n−1)∗(m−1) 個數，每個數可以填 [ 1 , k ] [1,k] [1,k]，是以是 k ( n − 1 ) ∗ ( m − 1 ) k^{(n-1)*(m-1)} k(n−1)∗(m−1) 種。最後我們隻考慮了一個地方的好格子，一共有 m ∗ n m*n m∗n個地方，是以還要乘以 m ∗ n m*n m∗n。

  綜上，最後的答案就是這個

n ∗ m ∑ i = 2 k ( i − 1 ) n − 1 + m − 1 k ( n − 1 ) ∗ ( m − 1 ) + k m ∗ n n*m\sum_{i=2}^{k}(i-1)^{n-1+m-1}k^{(n-1)*(m-1)}+k^{m*n} n∗mi=2∑k​(i−1)n−1+m−1k(n−1)∗(m−1)+km∗n

代碼

#include <iostream>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll pow_m(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1) res = res * a%mod;
		a = a * a%mod;
		b >>= 1;
	}
	return res;
}
int main()
{
	int t, ca = 1;
	scanf("%d", &t);
	while (t--)
	{
		ll n, m, k;
		scanf("%lld%lld%lld", &n, &m, &k);
		ll ans = 0;
		for (int i = 2; i <= k; i++)
			ans = (ans + pow_m(i - 1, n + m - 2)) % mod;
		ans = ans * n*m%mod;;
		ans = ans * pow_m(k, (n - 1)*(m - 1)) % mod;
		ans = (ans + pow_m(k, m*n)) % mod;
		printf("Case #%d: %lld\n",ca++, ans);
	}
	return 0;
}