题解 P3204【[HNOI2010]BUS 公交线路】

· · 题解

一、问题分析

====== 将问题转化为：一个N个数的序列，序列的每个位置需要填充一个[1,K]范围内的数。同时对于任意的1\leq i\leq K，序列的第i个位置已经被填充，填充的数为i。同时[N-K+1,N]区间内填充的数必须包含[1,K]的所有数。而「一辆公交车经过的相邻两个站台间距离不得超过Pkm」这个条件，等价于序列中任意一个长度为P的一段，都必须填充有[1,K]的所有数。

二、DP模型

====== 分析后可以得出，由于前K个填充的数已经确定，所以这里只关心序列中的数相同或不相同，而和具体数值无关。因此设f[i][S]为序列中[1,i-1]已经填充完，[i,i+P-1]这一段填充的状态为S的方案数。S是一个长度为P的01串，从高往低（之后的「第几位」都是从高位往低位）第j位为1表示位置i+j-1已经被填充，否则位置i+j-1还没被填充。

三、DP转移

====== 为了保证每个位置都能被填充，规定在转移过程中，S的第1位恒为1。同时由于[i,i+P-1]区间里必须有填充所有K个数，所以再规定在转移过程中S必须包含且仅包含K个1。

而判断S_2能否从S_1转移，就是把S_1最高位的1去掉之后在末尾再补一个0（记为S_3），如果S_3中的K-1个1能够恰好与S_2中K个1其中K-1个一一对应，，那么S_2能从S_1转移。

四、矩阵优化

====== 考虑到N\leq 10^9的数据范围，想到矩阵乘法。这时根据上面推出的转移条件，得到有用的状态只有C_{P-1}^{K-1}个。可以得到矩阵规模的最大值为C_9^{\lfloor\frac{9}{2}\rfloor}=126。

复杂度O((C_{P-1}^{K-1})^3\log N)。

五、代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 134, ZZQ = 30031;
int n, K, P, tot, sta[N];
struct cyx {
    int n, m, a[N][N];
    cyx() {}
    cyx(int _n, int _m) :
        n(_n), m(_m) {memset(a, 0, sizeof(a));}
    friend inline cyx operator * (cyx a, cyx b) {
        int i, j, k; cyx res = cyx(a.n, b.m);
        for (i = 1; i <= res.n; i++) for (j = 1; j <= res.m; j++)
        for (k = 1; k <= a.m; k++)
            (res.a[i][j] += a.a[i][k] * b.a[k][j]) %= ZZQ;
        return res;
    }
    friend inline cyx operator ^ (cyx a, int b) {
        int i; cyx res = cyx(a.n, a.m);
        for (i = 1; i <= res.n; i++) res.a[i][i] = 1;
        while (b) {
            if (b & 1) res = res * a;
            a = a * a;
            b >>= 1;
        }
        return res;
    }
} Orz, Zzq;
int main() {
    int i, j, k; cin >> n >> K >> P;
    for (i = (1 << P - 1); i < (1 << P); i++) {
        int cnt = 0; for (j = 0; j < P; j++) if ((i >> j) & 1) cnt++;
        if (cnt == K) sta[++tot] = i;
    }
    Orz = cyx(tot, tot); Zzq = cyx(tot, 1);
    for (i = 1; i <= tot; i++) for (j = 1; j <= tot; j++) {
        int S1 = sta[i], S2 = sta[j]; S1 = S1 - (1 << P - 1) << 1;
        for (k = 0; k < P; k++) if (!((S1 >> k) & 1) && S1 + (1 << k) == S2)
            Orz.a[j][i] = 1;
    }
    Zzq.a[tot][1] = 1; Orz = (Orz ^ n - K) * Zzq;
    cout << Orz.a[tot][1] << endl;
    return 0;
}
====