[HNOI2010]BUS 公交线路

题面

Bzoj

Sol

状压很显然
重点在于转移：题目就相当与每\(p\)长度的车站必须有且仅有\(k\)个被经过
那么转移时状压的二进制一定要有\(k\)个一
且两个相邻转移的状态之间必须满足：设为\(i->j\)，则\((i >> 1) \&j\)要有\(k-1\)个\(1\)
然后就可以加上矩阵快速幂优化，注意把满足要求的状态记下来，只有一百多个

我常数丑是我的错

# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int Zsy(30031);

IL int Input(){
    RG int x = 0, z = 1; RG char c = getchar();
    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return x * z;
}

int n, k, p, cnt[1024], que[150], len, pos;

IL void Up(RG int &x, RG int y){
    x += y;
    if(x >= Zsy) x -= Zsy;
}

struct Matrix{
    int a[150][150];

    IL Matrix(){
        Fill(a, 0);
    }
    
    IL int* operator [](RG int x){
        return a[x];
    }

    IL void Init(){
        for(RG int i = 0; i < len; ++i) a[i][i] = 1;
    }

    IL Matrix operator *(RG Matrix B){
        RG Matrix C;
        for(RG int i = 0; i < len; ++i)
            for(RG int j = 0; j < len; ++j)
                for(RG int l = 0; l < len; ++l)
                    Up(C[i][l], 1LL * a[i][j] * B[j][l] % Zsy);
        return C;
    }
} S, E, T;

int main(RG int argc, RG char* argv[]){
    n = Input(), k = Input(), p = Input();
    for(RG int i = 0; i < (1 << p); ++i){
        for(RG int x = i; x; x -= x & -x) ++cnt[i];
        if(cnt[i] == k && (i & 1)) que[len++] = i;
    }
    for(RG int i = 0; i < len; ++i)
        if(que[i] == (1 << k) - 1) pos = i;
    for(RG int i = 0; i < len; ++i)
        for(RG int j = 0; j < len; ++j)
            if(cnt[(que[i] >> 1) & que[j]] == k - 1) T[i][j] = 1;
    E.Init(), S[0][pos] = 1;
    for(RG int i = n - k; i; i >>= 1, T = T * T)
        if(i & 1) E = E * T;
    S = S * E;
    printf("%d\n", S[0][pos]);
    return 0;
}