標籤：

信息學競賽

基礎知識複習

03-18

本人只是個民科>_<，不科學的地方請輕噴。

TCO14 WildCard CountTables

題意：

$N imes M$ 的矩陣，每個格子可以染 $C$ 種顏色。

求有多少種染法使得任意兩行不完全相同，任意兩列不完全相同。

答案對 $10^9+7$ 取模。

$N,M,Cleqslant 2000$

題解：

考慮先讓任意兩列不完全相同。

把二項式反演改改。

$f_n=g_n-sum_{i=1}^{n-1}left[{natop i} ight]f_i$

SRM 686 CyclesNumber

題意：

令 $f(p,k)$ 為排列 $p$ 中環的數量的 $k$ 次冪。

給定 $n,k$ ，記 $P_n$ 為全體長度為 $n$ 的排列的集合，求 $sum_{pin P_n}f(p,k)mod 10^9+7$

$nleqslant 10^5$

$kleqslant 300$

題解：

考慮用斯特林數轉成算下降冪。

於是要算從 $n$ 個位置中選 $k$ 個環的方案數 $f(n,k)$ （ $k$ 次選擇可區分）。

明智的選擇是把斯特林數改改，於是有遞推式

$f(n,k)=kf(n-1,k-1)+nf(n-1,k)$

TCO 2013 Round 3A TrickyInequality

題意：

求 $sum_{i=1}^m x_ileqslant s (x_i> 0)$ 且 $forall ileqslant n, x_ileqslant t$ 的解數模 $10^9+7$ 。

$mleqslant 10^9$

$m-100leqslant nleqslant m$

$tleqslant 10^5$

$sleqslant 10^{18}$

題解：

預備知識：

$x^{underline{n}}=sum_{k=0}^{n} (-1)^{n-k}left[{natop k} ight]x^k$

$x^n=sum_kleft{{natop k} ight}x^{underline k}$

$Delta^nf(x)=sum_{i=0}^dc_iinom{x}{i-n} ext{其中}f(x)=sum_{i=0}^dc_iinom{x}{i}$

考慮容斥，顯然答案為 $sum_{k=0}^n(-1)^kinom{n}{k}inom{s-kt}{m}$

$(-1)^kinom{n}{k}$ 不好化簡，我們考慮 $n$ 階差分，顯然有

$Delta^nf(x)=sum_{k=0}^{n}(-1)^{n-k}inom{n}{k}f(x+k)$

稍加處理就得到我們需要的形式，令 $f(x)=inom{s-xt}{m}$ ，所求即 $Delta^nf(0)$ ：

考慮將其轉化為牛頓級數，我們先試圖將 $f(x)$ 轉化成一個多項式，然後再轉化成牛頓級數。

下降冪可以用斯特林數很容易地轉化成多項式（公式 (1)）：

$inom{s-xt}{m}=frac{1}{m!}sum_{j=0}^{m}x^jsum_{i=j}^{m}(-1)^{m-i+j}inom{i}{j}left[{matop i} ight]t^js^{i-j}$

繼續轉化多項式（利用公式(2)），令多項式中 $x^i$ 的係數為 $a_i$ 。

$sum_{i=0}^{m}a_ix^i=sum_{j=0}^{m}inom{x}{j}sum_{i=j}^{m}a_ileft{ {i atop j} ight} j!$

於是得到牛頓級數，令 $inom{x}{i}$ 的係數為 $b_i$ ，則 $b_n$ 為所求（公式(3)）。

將 $a_i$ 代入，最終得到：

$sum_{k=0}^{n} (-1)^k inom{n}{k} inom{s-kt}{m}=frac{n!(-1)^{n+m} t^n}{m!} sum_{i=0}^{m-n} sum_{j=0}^{m-n-i} (-1)^j inom{n+i+j}{j} left{ {n+i atop n} ight} left[{matop n+i+j} ight] t^i s^j$

最後只剩下快速計算斯特林數的問題了，注意到有 $n+i-nleq 100, m-n-i-jleq 100$ 。

我們考慮斯特林數的組合意義。

第二類斯特林數表示將 $n$ 個元素分為 $k$ 個非空子集的方案數。

容易發現至多只有 $n-k$ 個子集的大小大於 $1$ 。

我們暴力枚舉大於 $1$ 的子集個數，則有：

$left{ {n atop k} ight}=sum_{i=0}^{n-k}inom{n}{n-k+i}g(n-k+i,i)$

其中 $g(n,k)$ 為將 $n$ 個元素分為 $k$ 個大小大於 $1$ 的子集的方案數。

考慮第 $n$ 個元素要麼與此前一個元素一起成為一個新集合，要麼加入之前的集合，則有 $g(n,k)=kg(n-1,k)+(n-1)g(n-2,k-1)$ 。

第一類斯特林數表示將 $n$ 個元素分為 $k$ 個非空環排列的方案數。

類似第二類斯特林數，有

$left[{natop k} ight]=sum_{i=0}^{n-k}inom{n}{n-k+i}f(n-k+i,i)$

其中 $g(n,k)$ 為將 $n$ 個元素分為 $k$ 個大小大於 $1$ 的環排列的方案數。

我們用一個序列表示這些環排列，每個環排列我們令其中最小的元素排在第一個，排列之間用一個特殊元素分割，考慮第 $n$ 個元素要麼與此前一個元素一起成為一個新環排列，要麼插入之前的環排列構成的序列，則有： $f(n,k)=(n-1)f(n-1,k)+(n-1)f(n-2,k-1)$

推薦閱讀：

TAG:信息學競賽 |