HNOI2010 公交线路

未分类

通过样例可以得知题意中的第 $i$ 个始发站发第 $i$ 列车。那么题意可以解读为将 $n-k$ 个格子填上 $k$ 数，最后 $K$ 个格子需要有所有的数，每个长度为 $P$ 的子区间都必须包含所有的数。发现 $P$ 很小，所以设 $f(i,j)$ 为前 $i-1$ 个格子已经填完，后 $P$ 个格子的是否填涂的二进制状态。为了满足题目的限制，强制 $j$ 的二进制第一位是 $1$，总共有 $k$ 个一。那么 $f(i,j)$ 能从 $f(i-1,k)$ 转移过来的条件就是 $k$ 去掉第一位后面补上一个零后只与 $j$ 有一个二进制位不一样（$k$ 是零 $j$ 是一）。然后矩阵快速幂就完事了。

#include <iostream>
#include <cstdio>
#include <cstring>
const int MOD = 30031;
int n, K, P, cnt;
int S[256];
struct Matrix {
  int a[127][127];
  Matrix() {
    memset(a, 0, sizeof(a));
  }
  friend Matrix operator* (const Matrix &lhs, const Matrix &rhs) {
    Matrix res;
    for (int i = 1; i <= 126; ++i) {
      for (int j = 1; j <= 126; ++j) {
        for (int k = 1; k <= 126; ++k) {
          res.a[i][j] = (res.a[i][j] + (lhs.a[i][k] * rhs.a[k][j]) % MOD) % MOD;
        }
      }
    }
    return res;
  }
} dp, d, ans;
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
Matrix quickPow(Matrix x, int y) {
  Matrix res = x, base = x;
  --y;
  while (y > 0) {
    if (y & 1) res = res * base;
    base = base * base;
    y >>= 1;
  }
  return res;
}
int main() {
  n = read();
  K = read();
  P = read();
  int ansPos = 0;
  for (int i = 1 << (P - 1); i < 1 << P; ++i) {
    int tmp = i, sum = 0;
    while (tmp > 0) sum += (tmp & 1), tmp >>= 1;
    if (sum == K) S[++cnt] = i;
    if (i == ((1 << K) - 1) << (P - K)) dp.a[1][cnt] = 1, ansPos = cnt;
  }
  for (int i = 1; i <= cnt; ++i) {
    for (int j = 1; j <= cnt; ++j) {
      int tmp = S[i] ^ (1 << (P - 1)), sum = 0;
      tmp = (tmp << 1) ^ S[j];
      while (tmp > 0) sum += (tmp & 1), tmp >>= 1;
      if (sum == 1) {
        d.a[i][j] = 1;
      }
    }
  }
  dp = dp * quickPow(d, n - K);
  printf("%d\n", dp.a[1][ansPos]);
  return 0;
}