形態形成場（矩陣乘法優化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; }

轉載于:https://www.cnblogs.com/MyNameIsPc/p/9362107.html

總結

以上是生活随笔為你收集整理的形态形成场（矩阵乘法优化dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。