HNOI2010 公交线路

题目:

   小Z所在的城市有个公交车站,排列在一条长为公里的直线上,从左到右依次编号为,相邻公交车站间的距离均为公里。 作为公交车线路的规划者,小Z调查了市民的需求,决定按以下规则设计线路:
   1.设共有辆公交车,则号车站作为始发站,号车站作为终点站。
   2.每个车站必须被一辆且仅一辆公交车经停(始发站和终点站也算被经停)。
   3.公交车只能从编号较小的车站驶向编号较大的车站。
   4.一辆公交车经停的相邻两个车站间的距离不得超过公里。
   注意“经停”是指经过并停车,因经过不一定会停车,故经停与经过是两个不同的概念。在最终确定线路之前,小Z想知道有多少种满足要求的方案。由于答案可能很大,你只需求出答案对取模的结果。

思路:

   因为 很小,所以不难想到状压。设 表示最后一辆车在第 个点,后 个点是否被经停的状态为 的方案数。这样的合法状态只有不到 种,再用矩阵优化一下转移,复杂度

代码:

#include <bits/stdc++.h>
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int MOD = 30031, M = 130;

struct Matrix {
    int a[M][M], n, m;
    void clear() {mset(a, 0);}
    int* operator[] (int x) {return a[x];}
    Matrix operator* (Matrix b) {
        Matrix c;
        c.clear(); c.n = n; c.m = b.m;
        rep(i, 1, c.n) rep(j, 1, c.m) 
            rep(k, 1, m) 
                (c[i][j] += (ll) a[i][k] * b[k][j] % MOD) %= MOD;
        return c;
    }
} mt, dp;

Matrix qkpow(Matrix a, int k) {
    Matrix ans = a; k--;
    for(; k; k >>= 1, a = a * a)
        if(k & 1) ans = ans * a;
    return ans;
}

map<int, int> id;
int n, p, k, que[M], bin[M];
bool mark[M];
void init() {
    int st = (1 << k) - 1, tot = 0;
    int hed = 1, tai = 0;
    id[st] = ++tot; bin[tot] = st;
    que[++tai] = tot; mark[tot] = true;
    while(hed <= tai) {
        int x = que[hed++], o = bin[x];
        for(int i = 0; i <= p; i++) {
            if(~o >> i & 1) {
                int t = (o | (1 << i)) >> 1, y;
                if(~t & 1) continue;
                if(!id[t]) {id[t] = ++tot; bin[tot] = t;}
                y = id[t];
                mt[x][y] = 1;
                if(!mark[y]) {
                    que[++tai] = y;
                    mark[y] = true;
                }
            }
        }
    }
    mt.n = mt.m = dp.n = tot;
    dp.m = 1; dp[1][1] = 1;
    // * printf("%d\n", tot); tot = 126
}

int main() {
    File(bus);
    scanf("%d%d%d", &n, &k, &p);
    mt.clear();
    init();
    printf("%d\n", (qkpow(mt, n - k) * dp)[1][1]);
    return 0;
}