BZOJ 2004 公交线路

题意：

一个\(N\)个数的序列，每个位置上要填一个数\(x\in[1,K],x\in Z\)，

且规定\([N-K+1,N]\)，内包\([1,K]\)的所有数，且序列中任意长度为\(P\)的一段都包含了\([1,K]\)中每个数。

其中\(N\leq10^9,P\leq10,K\leq8,K\leq P\)

Solution

先抛开\(N\)不管，凭\(N,K\)范围可以确定是状压。

状态要连续， 并且我们注意到了只有状态里有\(K\)个\(1\)时状态才合法。

定义\(f[i][S]\)为已经填充了之前的\(i-1\)位，第\(i\)到\(i+P-1\)位的状态为\(S\)。

现在有任意\(S_1,S2\)，其中都有\(K\)位为1，

\(S_1\)丢掉最前面的一位然后左移一位后，拥有\(K-1\)个\(1\)。

如果这\(K-1\)个\(1\)与\(S_2\space K\)个\(1\)其中任意\(K-1\)个匹配的话就可以转移。

因为已经固定了\(S\)的第一位一定为\(1\)，所以合法状态总数一定不会超过\(max(C_{P-1}^{N-1})=126\)

当前复杂度为\(O(n\times 126^2)\)

再次观察\(N\)的范围和状态转移，我们发现状态转移可以用矩阵乘表示出来

转移矩阵\(G[j][i]\)表示状态\(j\)从状态\(i\)转移过来产生的贡献，合法情况下每个状态贡献恒定为\(1\)倍。

\(G\)自转移\(N-K\)次即可。

时间复杂度\(O((C_{P-1}^{K-1})^3\times log_2^N)\)

#include<cstdio>
#include<cctype>
#include<cstring>
const int N = 11; const int p = 30031;

struct Mat {
  int A[N*N+7][N*N+7]; int upmax = 126;
  inline void Mem1(){
    for (int i = 1; i <= upmax; i++) A[i][i] = 1;
  }
  inline void clear() {memset(A, 0, sizeof(A));}
};
int sta[1<<N];
Mat G;
inline Mat Mul(Mat A, Mat B) {
  Mat C; C.clear();
  for (int i = 1; i <= A.upmax; i++) for (int j = 1; j <= A.upmax; j++)
    for (int k = 1; k <= A.upmax; k++) {
      C.A[i][j] = C.A[i][j] + A.A[i][k] * B.A[k][j];
      C.A[i][j] = C.A[i][j] >= p ? C.A[i][j] - p : C.A[i][j];
    }
  return C;
}
inline Mat FST(Mat A, int k) {
  Mat C; C.clear(), C.Mem1();
  while (k) {
    if (k & 1) C = Mul(C, A); A = Mul(A, A), k >>= 1;
  } return C;
}
int n, K, P, tot = 0;
int main() {
  scanf ("%d%d%d", &n, &K, &P);
  int upmax = (1 << P) - 1;
  for (int S = (1 << (P -  1)); S <= upmax; S++) {
    int cnt = 0;
    for (int j = 0; j < P; j++) if (S & (1 << j)) cnt++;
    if (cnt == K) sta[++tot] = S;
  } G.clear();
  for (int i = 1; i <= tot; i++) for (int j = 1; j <= tot; j++) {
    int S1 = (sta[i] - (1 << (P - 1))) << 1, S2 = sta[j];
    for (int k = 0; k < P; k++) if (!((S1 >> k) & 1) && S1 + (1 << k) == S2)
      G.A[j][i] = 1;
  }
  Mat ss; ss.A[tot][1] = 1; G = Mul(FST(G, n - K), ss);
  printf ("%d", G.A[tot][1]);
}

BZOJ 2004 公交线路

原文：https://www.cnblogs.com/cjc030205/p/11638101.html