形态形成场（矩阵乘法优化dp）

时间：2020-12-13 13:31:35

形态形成场（矩阵乘法优化dp）

短信中将会涉及前\(k\)种大写字母，每个大写字母都有一个对应的替换式\(Si\)，替换式中只会出现大写字母和数字，比如\(A→BB,B→CC0,C→123\)，代表 \(A=12312301231230,B=1231230,C=123\)。现在对于给定的替换式，求字符 A 所代表的串有多少子串满足：

  • 这个子串为单个字符\(0\)或没有前导\(0\)。
  • 把这个子串看作一个十进制数后模\(n\)等于\(0\)。

答案对\(r\)取模。对于100%的数据，$2 \leq r \leq 10^9; 1 \leq k \leq 26; 4 \leq \left| S_i \right| \leq 100 $。

首先可以想出一个暴力dp：\(f[i][j]\)表示到第i位时，模n为j的串的个数，那么显然\(f[i][(10j+s[i])\%n]+=f[i-1][j]\)。复杂度是\(O(len\times n)\)。

但是这样只能拿60分，并不能过这道题。怎么办呢？观察一下题目，其实就是将一个字符的字符串展开以后dp，并且最多展开26层，同一个字符可能被展开多次。有没有想到矩阵优化dp？由于每次\(f[s[i]\%n]\)要加上1，因此不能用传统的矩阵递推数列，还必须在向量中加上一维常量1。为了方便，再在向量中加一维ans。向量长这样：

\((f_0, f_1, f_2,\dots,f_{n-1},ans,1)\)。

这样转移矩阵\(g[n+1][n+1]\)就可以被描述为：

\(\left [ \begin{matrix} & 第1列 & 第i列 & 第n列 & 第n+1列 \\第一行 & \dots & \dots & 1&0 \\ 第二行 & \dots & \dots & 0 & 0 \\ 第三行 & \dots & \dots & 0 & 0 \\ \dots \\ 第n行 & 0 & 0 & 1 & 0 \\ 第n+1行 & 0 & [s[i]=ch]*[ch!='0'] & 0 & 1\end{matrix} \right ]\)

先将矩阵进行处理，再把初始向量和矩阵相乘。\((0, 0, \dots,0, 1)*g[n+1][n+1]=(f_0, f_1, \dots,ans,1)\)，答案就是\(f_0+ans\)。由于初始向量只有第n+1项是1，所以\(f_0+ans=g[n+1][0]+g[n+1][n]\)。

注意单个字符0不能被漏掉统计，因此需要记录串中的0的个数。

#include <cctype>

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long LL;

const int maxk=30, maxn=40, maxl=105;

int n, r, k, zero[maxn];

char s[maxk][maxl];

struct Mat{

	int g[maxn][maxn];

}matrix[maxn], C;

void up(int &x, int y){ x+=y-r; x=(x<0?x+r:x); }

Mat& operator *(const Mat &A, const Mat &B){

	memset(C.g, 0, sizeof(C.g));

	for (int i=0; i<=n+1; ++i)

	for (int j=0; j<=n+1; ++j)

	for (int k=0; k<=n+1; ++k)

		up(C.g[i][j], 1ll*A.g[i][k]*B.g[k][j]%r);

	return C;

}

void build(int id){  //复合字符'A'+i 所对应的转移矩阵

	int len=strlen(s[id]), num;

	Mat &now=matrix[id], trans;

	for (int i=0; i<=n+1; ++i) now.g[i][i]=1;  //相当于直接让转移矩阵相乘

	for (int i=3; i<len; ++i){

		if (isdigit(s[id][i])){

			num=s[id][i]-'0';

			memset(trans.g, 0, sizeof(trans.g));

			trans.g[0][n]=trans.g[n][n]=trans.g[n+1][n+1]=1;

			for (int j=0; j<n; ++j) trans.g[j][(j*10+num)%n]=1;

			if (num) trans.g[n+1][num%n]=1;

			else up(zero[id], 1);

			now=now*trans;

		} else {

			num=s[id][i]-'A';

			now=now*matrix[num];

			up(zero[id], zero[num]);

		}

	}

}

int main(){

	scanf("%d%d%d", &n, &r, &k);

	for (int i=0; i<k; ++i) scanf("%s", s[i]);

	for (int i=k-1; ~i; --i) build(i);

	int ans=zero[0]; up(ans, matrix[0].g[n+1][0]);

	up(ans, matrix[0].g[n+1][n]);

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

	return 0;

}

相关文章