短信中将会涉及前 \(k\) 种大写字母, 每个大写字母都有一个对应的替换式 \(Si\), 替换式中只会出现大写字母和数字, 比如 \(ABB,BCC0,C123\), 代表 \(A=12312301231230,B=1231230,C=123\). 现在对于给定的替换式, 求字符 AA 所代表的串有多少子串满足:
这个子串为单个字符 \(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;
- }
来源: http://www.bubuko.com/infodetail-2698708.html