@hdu - 6372@ sacul

目錄

• @description@
• @solution@
• @accepted code@
• @details@

---

@description@

定義矩陣 \(A_i\) 是一個大小為 \(p^i*p^i\) 的矩陣，其中 \(p\) 是第 \(c\) 個素數（c 給定），且 \(A_i[x][y] = [C(x, y) \mod p > 0]\)（其中 C(x, y) 是組合數）。
行列從 0 開始計數。

再定義 \(F[i][j]\) 表示 \((A_i)^j\) 中所有元素之和。

求 \(\sum_{i=1}^n\sum_{j=1}^{k}F[i][j]\)。對 10^9 + 7 取模。

Input
第一行包含一個整數 T，然后接下來是 T 組數據：
每一組數據包含三個整數 c, n, k (0 < n ≤ 10^9, 0 < c, k ≤ 10^5)。意義如上。

Output
對于每組數據，輸出一個整數表示答案。

Sample Input
1
1 1 1
Sample Output
3

@solution@

看上去這個題非常不可做，先定義了一個矩陣，然后又要求矩陣冪，然后又要把這個矩陣冪中所有元素求和，然后又要把這些矩陣求和的結果再求和。
但是你只需要找到突破口，剩下的部分就一氣呵成（其實一氣呵成這個詞不能這么用。。。今年中考考了這玩意兒，然后做錯了，所以印象深刻。。。）
怎么找突破口？你只需要把題目倒過來讀注意到矩陣的定義涉及到組合數對素數取模，于是就可以牽扯出 lucas 定理。

lucas 定理是什么？其實很簡單。對于 \(C(n, m) \mod p\)，我們將 n, m 拆成 p 進制數的形式，即 \(n = n_0 + n_1*p^1 + ..., m = m_0 + m_1*p^1 + ...\)。
于是 lucas 定理告訴我們：\(C(n, m) = C(n_0, m_0)*C(n_1, m_1)*... \mod p\)
證明這個定理也不難，只是與這道題無關所以暫且不提。

很顯然 \(C(n, m) \mod p \ge 0\)，所以我們只需要判斷 \(C(n, m) \mod p = 0\) 是否成立即可。
又因 \(n_i < p, m_i < p\) （因為是 p 進制嘛），所以 \(C(n_i, m_i)\) 不可能含因子 p，故我們只需要對于每一個 i 判斷是否 \(C(n_i, m_i) = 0\)，而前面那個等價于 \(n_i > m_i\)。
所以 \(A_i[x][y]\) 為 1 等價于在 p 進制下 x 的每一位都 ≤ y 的對應位。

現在考慮 \((A_i)^j[x][y]\) 怎么求。
先試著考慮 \((A_i)^2[x][y]\)，可以發現 \((A_i)^2[x][y] = \sum_{z}A_i[x][z]*A_i[z][y]\)，只有當 \(A_i[x][z], A_i[z][y]\) 都為 1 時才會產生貢獻。
這有點兒像偏序的關系，因為有些傳遞性和偏序形成鏈的感覺在里面。
或者用圖論的語言，如果 \(A_i[x][y] = 1\) 則 x 向 y 連邊。則 \((A_i)^2[x][y]\) 則有點兒像走兩步（中途可以停留在原地）從 x 到達 y 的方案數。
從而簡單推廣，可以得到 \((A_i)^j[x][y]\) 表示走 j 步從 x 到達 y 的方案數。

那么 F[i][j] 的含義是什么？為了計數的方便我們暫且不用圖論的語言描述。
F[i][j] 表示長度為 i 的 p 進制的數字串，選出 j+1 個記為 s0, s1, ... sj，對于第 x 位（1≤x≤n）始終滿足 s0[x] ≤ s1[x] ≤ ... ≤ sj[x] 的方案總數。
怎么求 F[i][j] 呢？其實也比較簡單。因為每一位都是獨立的，所以考慮某一位然后乘法原理乘起來即可。
我們發現如果確定了 s0[x], s1[x], ..., sj[x] 分別是哪些數，它們的順序始終是一定的（即排序過后的順序）。所以我們相當于是求 x1 + ... + xp = j + 1 的非負整數解的個數。經典的組合數學問題，答案為 C(j+p, j+1)。
于是 F[i][j] = C(j+p, j+1)^i。

于是 \(\sum_{i=1}^n\sum_{j=1}^{k}F[i][j] = \sum_{i=1}^n\sum_{j=1}^{k}C(j+p, j+1)^i = \sum_{j=1}^{k}\sum_{i=1}^nC(j+p, j+1)^i\)。
枚舉 j 然后等比數列求和即可。
注意 C(j+p, j+1) 與 C(j+p+1, j+1+1) 之間實際上是有倍數的關系（你可以把它們拆成階乘形式以觀察到這一點）。于是我們可以直接遞推而不用預處理階乘。

@accepted code@

#include<cstdio>
const int MAXM = 1299709;
const int MOD = int(1E9) + 7;
int pow_mod(int b, int p) {int ret = 1;while( p ) {if( p & 1 ) ret = 1LL*ret*b%MOD;b = 1LL*b*b%MOD;p >>= 1;}return ret;
}
int prm[MAXM + 5], pcnt;
bool nprm[MAXM + 5];
void init() {for(int i=2;i<=MAXM;i++) {if( !nprm[i] )prm[++pcnt] = i;for(int j=1;1LL*i*prm[j]<=MAXM;j++) {nprm[i*prm[j]] = true;if( i % prm[j] == 0 )break;}}
}
int solve(int p, int n, int k) {int ans = 0, tmp = p;for(int j=1;j<=k;j++) {tmp = 1LL*tmp*(j + p)%MOD*pow_mod(j + 1, MOD - 2)%MOD;if( tmp == 1 )ans = (ans + n)%MOD;else ans = (ans + 1LL*(pow_mod(tmp, n + 1) - 1)*pow_mod(tmp - 1, MOD-2)%MOD - 1)%MOD;}return (ans + MOD)%MOD;
}
int main() {init();int T; scanf("%d", &T);for(int i=1;i<=T;i++) {int c, n, k; scanf("%d%d%d", &c, &n, &k);printf("%d\n", solve(prm[c], n, k));}
}

@details@

似乎總喜歡廢話很多。。。明明一個不是很復雜的題目卻寫了這么多東西。。。

這道題有一個點就是：等比數列要特判公比為 1 的情況。
。。。雖然數學上經常考這個東西，不過還是沒記住。。。