BZOJ2004:公交线路优化（状态压缩DP与矩阵快速幂）

在处理公交线路问题时，一个关键点在于每个路线相邻车站的距离不超过K。这意味着我们可以通过对连续K个车站的状态进行状态压缩（状压）来简化问题。

具体实现上，我们首先使用状态压缩动态规划（状压DP）方法来构建状态转移方程。由于直接进行大规模的DP可能会导致效率低下，因此我们引入了矩阵快速幂技术来加速这一过程。

以下是具体的代码实现：

#include 
#include 
#include 
#include 

#define MAXN 140
#define MOD 30031

using namespace std;

struct Matrix {
    int num[MAXN][MAXN];
    int n, m; // n*m size matrix
    void setOne(int a, int b) {
        n = a, m = b;
        for (int i = 1; i <= min(n, m); i++) num[i][i] = 1;
    }
    Matrix() { memset(num, 0, sizeof(num)); }
} T, A, one;

Matrix operator*(Matrix a, Matrix b) {
    Matrix c;
    c.n = a.n, c.m = b.m;
    for (int i = 1; i <= c.n; i++)
        for (int j = 1; j <= c.m; j++)
            for (int k = 1; k <= a.m; k++)
                c.num[i][j] = (c.num[i][j] + a.num[i][k] * b.num[k][j]) % MOD;
    return c;
}

Matrix fastPow(Matrix base, int pow) {
    Matrix ans;
    ans.setOne(base.n, base.m);
    while (pow) {
        if (pow & 1) ans = ans * base;
        base = base * base;
        pow >>= 1;
    }
    return ans;
}

int calc(int x) { // 计算x的二进制中1的个数
    int sum = 0;
    while (x) {
        sum++;
        x -= x & (-x); // 去掉x的最后一个1
    }
    return sum;
}

int n, k, p, goal; // goal为目标状态

bool canConvert(int to, int from) { // 检查状态from能否一步转移到状态to
    from = (from - (1 <<(p - 1))) <<1; // 将from向左移一位，个位用0补齐
    int tmp = from ^ to; // tmp应该只有一个1
    if (tmp == (tmp & (-tmp))) return true; // tmp只有一个1，则是合法的
    return false; // 否则是不合法的
}

int status[MAXN], top = 0; // 保存所有DP过程中可能出现的状态的栈

int main() {
    scanf("%d%d%d", &n, &k, &p);
    for (int S = (1 <<(p - 1)); S <(1 <