這題比賽時(shí)候過(guò)得很糾結(jié)……最后還是學(xué)長(zhǎng)過(guò)的……比賽時(shí)候腦子可能不夠清楚，一直WA……
首先，這個(gè)題要分成兩個(gè)部分解決：
第一部分：從n個(gè)東西里面取出r個(gè)，每個(gè)間距至少為 k （1～K不行，1～K ＋ 1行）
第二部分：將這r個(gè)東西分成至多m組，可以有空組
第二部分貌似好久之前搞OI的時(shí)候干過(guò)……貼過(guò)來(lái)：
N球放在M個(gè)盒子里，求共有多少種放法
但是有3個(gè)不同的條件 ：N個(gè)球是否相同，M個(gè)盒子是否相同，是否允許有盒子空著
|
球和球
|
盒和盒
|
空盒
|
情況數(shù)
|
|
有區(qū)別
|
有區(qū)別
|
有空盒
|
mn
|
|
有區(qū)別
|
有區(qū)別
|
無(wú)空盒
|
M！s（n,m）
|
|
有區(qū)別
|
無(wú)區(qū)別
|
有空盒
|
S(n,1)+s(n,2)+…+s(n,m),n>=m
S(n,1)+s(n,2)+…+s(n,n),n<=m
|
|
有區(qū)別
|
無(wú)區(qū)別
|
無(wú)空盒
|
S(n,m)
|
|
無(wú)區(qū)別
|
有區(qū)別
|
有空盒
|
C(n+m-1,n)
|
|
無(wú)區(qū)別
|
有區(qū)別
|
無(wú)空盒
|
C(n-1,m-1)
|
|
無(wú)區(qū)別
|
無(wú)區(qū)別
|
有空盒
|
F(m,n)
|
|
無(wú)區(qū)別
|
無(wú)區(qū)別
|
無(wú)空盒
|
F(m,n-m)
|
|
然后，其中的F(m,n)貌似是當(dāng)時(shí)寫過(guò)的一個(gè)DP，S(M,N)是第二類stirling數(shù)……
遞推公式：
1 int S(int n,int m) {
2 if (n == m || m == 1) return 1;
3 return m * S(n - 1, m) + S(n - 1, m - 1);
4 }
第一部分：可以看作這么一個(gè)生成函數(shù)的相關(guān)問(wèn)題：由于每個(gè)東西之間都隔了>=K－1的一段距離，因此一個(gè)可行解可以看作，長(zhǎng)度為K，K + 1，K + 2的棍子r － 1個(gè)（我們認(rèn)為每個(gè)棍子的頭是我們?nèi)〉狞c(diǎn)），拼接成長(zhǎng)度為L(zhǎng)en的一個(gè)大段，之后再堵上一個(gè)，就是一個(gè)Len ＋１的可行解……
而r - 1根棍子，拼成長(zhǎng)度為L(zhǎng)en 的可行解數(shù)目，就是(X^K + X^(K + 1) + X^(K + 2) + .....) ^ (r - 1)，這個(gè)多項(xiàng)式，展開(kāi)之后，X^Len項(xiàng)前面的系數(shù)……
不過(guò)……由于數(shù)據(jù)范圍，直接搞是不成的……
于是提取，變形：X^(K * (r - 1)) * (1 + X + X^2 + X ^3 +....)^(r - 1)
然后再變形：X^(K * (r - 1)) * (1/(1 - x))^(r - 1)……
然后參照Matrix67大神的日志，展開(kāi)后面那項(xiàng)：
1/(1-x)^n=1+C(n,1)x^1+C(n+1,2)x^2+C(n+2,3)x^3+...+C(n+k-1,k)x^k+...
我們知道，要求長(zhǎng)度為len的可行數(shù)目，也就是要X^Len項(xiàng)前面的系數(shù)，然后，由于前面提取出來(lái)了一個(gè)K * (r - 1)，也就是去后面找len - K * (r - 1) 項(xiàng)的系數(shù)……
也就是說(shuō)，令pow = len - K * (r - 1)，答案就是C(r - 1 + pow - 1, pow)……
不過(guò)這還沒(méi)完，因?yàn)樵蹅円闯傻拈L(zhǎng)度是len，而總的長(zhǎng)度是N，需要乘上這個(gè)長(zhǎng)度len的開(kāi)頭位置的可能數(shù)……
另外還需要特殊處理：咱們?cè)谔幚淼臅r(shí)候，是先用r - 1個(gè)拼接成長(zhǎng)度為L(zhǎng)en的一個(gè)大段，再堵上最后一個(gè)……當(dāng)r == 1需要特判……
代碼：
1 #include <cstdio>
2 #include <cstring>
3
4 typedef long long Long;
5 const Long MOD = 1000000007;
6
7 Long F[1010][1010];
8 Long C[2010][2010];
9 Long S(int n,int m) {
10 if (n == m || m == 1) return 1LL;
11 if (F[n][m] > 0) return F[n][m];
12 return F[n][m] = (m * S(n - 1, m) % MOD + S(n - 1, m - 1)) % MOD;
13 }
14 void init() {
15 for (int i = 0; i <= 2000; i++) {
16 for (int j = 0; j <= i; j++) {
17 if (j == 0) C[i][j] = 1;
18 else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
19 }
20 }
21 }
22 int n,r,k,m;
23
24 int main() {
25 memset(F,0xff,sizeof(F));
26 init();
27 while (scanf("%d%d%d%d",&n,&r,&k,&m) > 0) {
28 if (r == 1) {printf("%d\n",n); continue;}
29 Long ans = 0;
30 for (int i = 1; i <= m && i <= r; i++) {
31 ans = (ans + S(r,i)) % MOD;
32 }
33 Long tmp = 0;
34 for (int len = k * (r - 1); len < n; len++) {
35 int left = n - len;
36 int pow = len - k * (r - 1);
37 // r > 1 !!
38 tmp = (tmp + left * C[r - 1 + pow - 1][pow]) % MOD;
39 }
40 ans = ans * tmp % MOD;
41 printf("%lld\n",ans);
42 }
43 return 0;
44 }