【BZOJ2004】[Hnoi2010]Bus 公交線路 狀壓+矩陣乘法

【BZOJ2004】[Hnoi2010]Bus 公交線路

Description

小Z所在的城市有N個公交車站，排列在一條長(N-1)km的直線上，從左到右依次編號為1到N，相鄰公交車站間的距離均為1km。 作為公交車線路的規劃者，小Z調查了市民的需求，決定按下述規則設計線路：

1.設共K輛公交車，則1到K號站作為始發站，N-K+1到N號臺作為終點站。

2.每個車站必須被一輛且僅一輛公交車經過（始發站和終點站也算被經過）。?

3.公交車只能從編號較小的站臺駛往編號較大的站臺。?

4.一輛公交車經過的相鄰兩個

站臺間距離不得超過Pkm。 在最終設計線路之前，小Z想知道有多少種滿足要求的方案。由于答案可能很大，你只需求出答案對30031取模的結果。

Input

僅一行包含三個正整數N K P，分別表示公交車站數，公交車數，相鄰站臺的距離限制。

N<=10^9，1<P<=10，K<N，1<K<=P

Output

僅包含一個整數，表示滿足要求的方案數對30031取模的結果。

Sample Input

樣例一：10 3 3
樣例二：5 2 3
樣例三：10 2 4

Sample Output

1
3
81

HINT

【樣例說明】

樣例一的可行方案如下： (1,4,7,10)，(2,5,8)，(3,6,9)

樣例二的可行方案如下： (1,3,5)，(2,4) (1,3,4)，(2,5) (1,4)，(2,3,5)?

P<=10 , K <=8

題解：看到P和K很小想到狀壓。用f[i][S]表示已經覆蓋了前i個車站，每個車的位置的狀態為S的方案數（S只包含前P個車站）。

由于n很大，考慮矩乘優化。我們將沒有用的狀態扔掉，最終矩陣大小是不超過$C_{10}^5\times C_{10}^5=252\times 252$的。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int P=30031;
int n,m,k,tot;
struct M
{int v[260][260];M () {memset(v,0,sizeof(v));}int * operator [] (int a) {return v[a];}M operator * (const M &a) const{M b;int i,j,k;for(i=1;i<=tot;i++)	for(j=1;j<=tot;j++)	for(k=1;k<=tot;k++)	b.v[i][j]=(b.v[i][j]+v[i][k]*a.v[k][j])%P;return b;}
}S,T;
int r[1<<10],cnt[1<<10];
inline void pm(int y)
{while(y){if(y&1)	S=S*T;T=T*T,y>>=1;}
}
int main()
{scanf("%d%d%d",&n,&k,&m);int i,j;for(i=1;i<(1<<m);i++){cnt[i]=cnt[i-(i&-i)]+1;if(cnt[i]==k)	r[i]=++tot;}for(i=1;i<(1<<m);i++)	if(r[i]){if(i&1)	T[r[i]][r[(i>>1)|(1<<(m-1))]]++;else	for(j=0;j<m;j++)	if((i>>j)&1)	T[r[i]][r[((i^(1<<j))>>1)|(1<<(m-1))]]++;}S[1][r[((1<<k)-1)<<(m-k)]]=1;pm(n-k);printf("%d",S[1][r[((1<<k)-1)<<(m-k)]]);return 0;
}