洛谷 P3204 [HNOI2010]公交线路

时间：2023-02-10 03:44:40

题面

luogu

题解

矩阵快速幂\(+dp\)

其实也不是很难

先考虑朴素状压\(dp\)

\(f[i][S]\) 表示最慢的车走到了\(i\)，\([i, p+i-1]\)的覆盖情况

状态第一位一定是\(1\)

那么显然\(f[i][S] = \sum f[i-1][S']\)（\(S'\)能转移到\(S\))

什么情况能转移呢？

假如:\(S1->S2\)

\(S1\)去掉第一位，再在后面补\(0\),产生的新数和\(S2\)至多只有一个差异

\(n\)很大，所以矩阵优化一下

先把合法的状态都弄出来

如果两个状态可以转移，\(Matrix[i][j] = 1\)

初始矩阵乘以一次\(Matrix\)，就转移了一次，快速幂算一下就可以啦

Code

#include<bits/stdc++.h>

#define LL long long

#define RG register

using namespace std;

template<class T> inline void read(T &x) {

    x = 0; RG char c = getchar(); bool f = 0;

    while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;

    while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();

    x = f ? -x : x;

    return ;

}

template<class T> inline void write(T x) {

    if (!x) {putchar(48);return ;}

    if (x < 0) x = -x, putchar('-');

    int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;

    for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;

}

const int Mod = 30031;

int N;

struct node {

	int a[150][150];

	node operator *(node A) const {

		node tmp;

		memset(tmp.a, 0, sizeof(tmp.a));

		for (int i = 1; i <= N; i++)

			for (int j = 1; j <= N; j++)

				for (int k = 1; k <= N; k++)

					(tmp.a[i][j] += a[i][k]*A.a[k][j]) %= Mod;

		return tmp;

	}

}X, s;

int S[150], len;

int n, k, p;

bool check(int s1, int s2) {

	s1 <<= 1;

	int tmp = 0;

	for (int i = 0; i < p; i++) if (((s1>>i)&1) ^ ((s2>>i)&1)) tmp++;

	return tmp < 2;

}

int main() {

	read(n), read(k), read(p);

	for (int i = 1<<(p-1); i < (1<<p); i++) {

		int cnt = 0;

		for (int j = 0; j < p; j++)

			if ((i >> j) & 1) cnt++;

		if (cnt == k) S[++len] = i;

	}

	for (int i = 1; i <= len; i++)

		for (int j = 1; j <= len; j++) {

			int S1 = S[i], S2 = S[j];

			if (check(S1, S2)) X.a[i][j] = 1;

		}

	int y = n-k;

	N = len;

	for (int i = 1; i <= N; i++)

		s.a[i][i] = 1;

	for (; y; y >>= 1, X = X*X) if (y&1) s = s*X;

	printf("%d\n", s.a[N][N]);

	return 0;

}

相关文章