【洛谷 P3193】 [HNOI2008]GT考试（KMP，dp，矩阵乘法）

题目链接

\(f[i][j]\)表示准考证号到第\(i\)位，不吉利数字匹配到第\(j\)位的方案数。

答案显然是\(\sum_{i=0}^{m-1}f[n][i]\)

\(f[i][j]=\sum_{k=1}^{m-1}f[i-1][k]*g[k][j]\)

\(g[i][j]\)表示不吉利数字匹配到第\(i\)位后加一个数字能匹配到第\(j\)位的方案数，因为这个数字是固定的，可以通过\(kmp\)求出来。

然后观察到\(f[i][j]\)的递推式是个矩阵，用矩阵快速幂加速即可。

#include <cstdio>

#include <cstring>

const int MAXM = 22;

char a[MAXM];

int nxt[MAXM], g[MAXM][MAXM], f[MAXM], tmp[MAXM][MAXM], temp[MAXM];

int n, m, mod, ans;

void gg(){

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

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

	   	  tmp[i][j] = 0;

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

	         (tmp[i][j] += g[i][k] * g[k][j]) %= mod;

	   }

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

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

	      g[i][j] = tmp[i][j];

}

void gf(){

	for(int i = 1; i <= m; ++i){

		temp[i] = 0;

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

		   (temp[i] += f[j] * g[j][i]) %= mod;

	}

	for(int i = 1; i <= m; ++i) f[i] = temp[i];

}

void fast_pow(int k){

	while(k){

		if(k & 1) gf();

		gg(); k >>= 1;

	}

}

int main(){

	scanf("%d%d%d%s", &n, &m, &mod, a + 1);

	int p = 0;

	for(int i = 2; i <= m; ++i){

	   while(a[i] != a[p + 1] && p) p = nxt[p];

	   if(a[i] == a[p + 1]) ++p;

	   nxt[i] = p;

	}

	for(int i = 0; i < m; ++i)

	   for(int j = '0'; j <= '9'; ++j){

	   	  int tmp = i;

	      while(a[tmp + 1] != j && tmp) tmp = nxt[tmp];

	      if(a[tmp + 1] == j) ++tmp;

	      if(tmp < m) ++g[i + 1][tmp + 1];

       }

    f[1] = 1;

    fast_pow(n);

	for(int i = 0; i <= m; ++i)

	   (ans += f[i]) %= mod;

	printf("%d\n", ans);

	return 0;

}

巴特西

【洛谷 P3193】 [HNOI2008]GT考试（KMP，dp，矩阵乘法）

最新文章

热门文章