BZOJ 2004|HNOI 2010 Day 1|公交線路|狀态壓縮動态規劃|矩陣乘法

公交線路

小 Z 所在的城市有 N 個公共汽車站,排列在一條長為 N−1 公裡的直線上,從左到右依次編号

為 1 到 N,相鄰公共汽車站間的距離均為 1 公裡。

作為公共汽車線路的規劃者,小 Z 調查了市民的需求,決定按以下規則設計線路:

1. 設共有 K 輛公共汽車,則 1 到 K 号車站作為始發站,N−K+1 到 N 号車站作為終點站。

2. 每個車站必須被一輛且僅一輛公共汽車經停(始發站和終點站也算被經停)。

3. 公共汽車隻能從編号較小的車站駛向編号較大的車站。

4. 一輛公共汽車經停的相鄰兩個車站間的距離不得超過 P 公裡。

注意“經停”是指經過并停車,因經過不一定會停車,故經停與經過是兩個不同的概念。

在最終确定線路之前,小 Z 想知道有多少種滿足要求的方案。由于答案可能很大,你隻需求出

答案對 30031 取模的結果。

輸入

輸入檔案隻有一行,其中包含用空格隔開的三個正整數N, K,

P,分别表示公共汽車站數,公共汽車數,一輛公共汽車經停的相鄰兩個車站間的最大距離。輸入的資料保證40%的資料滿足N≤1000。100%的資料滿足 1<N<109,1<P≤10,K<N,1<K≤P

輸出

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

樣例

sample input 1

10 3 3
           

sample output 1

1
           

sample input 2

5 2 3
           

sample output 2

3
           

sample input 3

10 2 4
           

sample output 3

81
           

樣例解釋

樣例一滿足要求的方案隻有1種,即:(1,4,7,10),(2,5,8),(3,6,9)。樣例二滿足要求的方案有3種,即:(1,3,5),(2,4);(1,3,4),(2,5)和(1,4),(2,3,5)。

題解

不看資料範圍不會做系列。。

發現 P 很小但N很大，于是狀壓。。

令

f[i][state]

表示從i開始連續P個位置的狀态為state的方案數。那麼狀态轉移方程很顯然。然後初始狀态是

f[1][{1~k号車站存在，k+1~p号車站不存在}]

，至于目标狀态，為了簡化情況，定為

f[n-k+1][{1~k号車站存在，k+1~p号車站不存在}]

，當然目标狀态寫到

f[n-p+1]

也可以，代碼稍長點就是了。。

#include <cstdio>
#include <cstring>
#define rep(i,j,k) for(int i=j;i<k;++i)
const int N = , P = ;
int s = , state[N];
struct Matrix {
    int c[N][N];
    Matrix(int x = ) { memset(c, , sizeof c); rep(i,,s) c[i][i] = x; }
    friend Matrix operator* (const Matrix &a, const Matrix &b) {
        Matrix c;
        rep(k,,s) rep(i,,s) rep(j,,s)
            (c.c[i][j] += a.c[i][k] * b.c[k][j]) %= P;
        return c;
    }
    friend Matrix operator^ (Matrix a, int b) {
        Matrix c();
        for (; b; b /= , a = a * a)
            if (b & ) c = c * a;
        return c;
    }
};

int count_bit(int x) {
    int s = ;
    for (; x; x -= x & -x) ++s;
    return s;
}

bool check(int x, int y) {
    x >>= ;
    int t = x ^ y;
    return t == (t & -t);
}

int main() {
    int n, k, p, x;
    scanf("%d%d%d", &n, &k, &p);
    for(int i=;i<(<<p);i+=) if (count_bit(i) == k) {
        state[s] = i; if (i == ( << k) - ) x = s;
        ++s;
    }
    Matrix a, b;
    rep(i,,s) rep(j,,s)
        if (check(state[i], state[j]))
            a.c[i][j] = ;
    b.c[][x] = ;
    printf("%d", (b * (a ^ (n - k))).c[][x]);
    return ;
}