P11030 『DABOI Round 1』Blessings Repeated题解
【形式化题意】
给定一个正整数 \(k\) 和两个字符串 \(S,T\)。
设字符串 \(s\) 为 \(k\) 个字符串 \(S\) 首尾相接得到的字符串，\(n=\vert s \vert , m=\vert T \vert\)。
设答案集合 \(P=\{ (i_0,i_1,\dots,i_{m-1}) \mid 0\le i_0 < i_1 < \dots < i_{m-1} < n, \forall~0 \le j < m, s_{i_j}=T_j \}\)，请求出 \(\vert P \vert \bmod 998244353\)。
输入格式
输入共 \(3\) 行。
第 \(1\) 行 \(1\) 个整数，表示 \(k\)。
第 \(2\) 行 \(1\) 个字符串，表示 \(S\)。
第 \(3\) 行 \(1\) 个字符串，表示 \(T\)。
输出格式
输出共 \(1\) 行 \(1\) 个整数，表示答案。
样例 #1
样例输入 #1
2
stocyhorz
cyh
样例输出 #1
4
样例 #2
样例输入 #2
4
c
ccc
样例输出 #2
4
提示
【样例 1 解释】
将 \(S\) 重复 \(2\) 次得到 \(\texttt{stocyhorzstocyhorz}\)。
答案集合 \(P=\{(3,4,5),(3,4,14),(3,13,14),(12,13,14) \}\)，因此 \(\vert P\vert=4\)。
【数据范围】
对于 \(100\%\) 的数据，\(0<k\le10^{18}\)，\(0 < \vert S \vert \le 5 \times 10^3\)，\(0 < \vert T \vert \le 10\)，字符串 \(S,T\) 均由小写英文字母组成。
| \(\text{Point}\) | \(k\le\) | \(\vert S\vert\le\) | \(\vert T\vert\le\) |
|---|---|---|---|
| \(1\sim2\) | \(10^{18}\) | \(5 \times 10^3\) | \(1\) |
| \(3\) | \(1\) | \(5 \times 10^3\) | \(2\) |
| \(4\sim5\) | \(100\) | \(5 \times 10 ^3\) | \(2\) |
| \(6\sim7\) | \(1\) | \(50\) | \(4\) |
| \(8\sim10\) | \(10\) | \(5 \times 10^3\) | \(10\) |
| \(11\sim20\) | \(10^{18}\) | \(5 \times 10^3\) | \(10\) |
赛时想法
想到了做一个 \(dp\) ，但是一上来就把阶段丢掉了，导致把自己绕晕了，大概想的是定义 \(dp[i]\) 为：如果 \(S\) 的当前位置位在 \(T\) 中，那么选完了这一位以后对应的方案数 ，\(i\) 代表 \(T\) 中对应的第 \(i\) 个字符。转移的时候就统计前缀和就行，但这样的想法很容易被 \(hack\) 掉，还是我太菜了，很显然的一个例子是 \(T=aaa\) ，当我们枚举到 \(S\) 中某位是 \(a\) 时，\(dp[2]\) 会从 \(dp[1]\) 进行转移，因此会多统计出来一部分。
正解
重新定义 \(dp[i][j]\) 为考虑完 \(S\) 中前 \(i\) 个后，选完 \(T\) 串中第 \(j\) 个位置的方案数，那么转移方程也十分的明显了。
\[dp[i][j] = \begin{cases} dp[i-1][j] ,& S[i]!=T[j]\\ dp[i-1][j]+dp[i-1][j-1],&S[i]==T[j]\\ \end{cases}\]发现 \(k\) 的数据范围尤其的大，基本上要么就是推数学结论，要么就是矩阵加速递推，现在 \(dp\) 都写出来了，这下不得不递推了。
核心思想
和普通的矩阵加速不同（很大可能是我刷的题太少了），本题的 \(dp\) 是带条件的，也就是说，在某一个循环内枚举的时候，有可能会有很多个不同的转移矩阵。
但最重要的地方在于，这些转移矩阵的出现是有规律的，如\((A_1 \cdot A_2\cdot...\cdot A_n)\cdot...\cdot(A_1 \cdot A_2\cdot...\cdot A_n)\) 一共有 \(k\) 个这样的循环，那么我们记每一个循环根据结合律得出的转移矩阵是 \(Sup\) ，总的转移矩阵就是 \(Sup^k\) 。
最后在初始 \(dp\) 矩阵右乘上一个 \(Sup^k\) 就好了。
容易犯错的地方
注意 \(dp[0]\) 的初值应该赋为 \(1\) ，不然答案为 \(0\) 了。
然后还有就是，由于每一个循环节内的子转移矩阵是不同的，所以累乘的方式应该根据 \(dp\) 是左乘还是右乘转移矩阵有所变化，比如下面给出的代码是左乘转移矩阵，那么在预处理的时候也应该从左边乘进来，类似于一个栈的结构。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=20;
struct Matrix
{
int n,m;
int a[N][N];
Matrix()
{
memset(a,0,sizeof(a));
}
void reset()
{
memset(a,0,sizeof(a));
}
void print()
{
for(int i=0;i<=n;++i)
{
for(int j=0;j<=m;++j)
printf("%lld ",a[i][j]);
putchar('\n');
}
}
};
Matrix I(int n)
{
Matrix tmp;
tmp.n=tmp.m=n;
for(register int i=0;i<=n;++i)tmp.a[i][i]=1;
return tmp;
}
const int MOD=998244353;
Matrix operator *(Matrix a,Matrix b)
{
Matrix tmp;
tmp.n=a.n,tmp.m=b.m;
for(register int i=0;i<=a.n;++i)
for(register int j=0;j<=b.m;j++)
for(register int k=0;k<=a.m;++k)
tmp.a[i][j]+=a.a[i][k]*b.a[k][j]%MOD,tmp.a[i][j]%=MOD;
return tmp;
}
inline Matrix power(Matrix a,int b)
{
Matrix ans=I(a.n);
while(b)
{
if(b&1)ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
int k,n;
char s[50000],t[100];
Matrix Ans,sup;
vector<int> rec[200];
inline void pre()
{
cin>>k;
cin>>s>>t;
n=strlen(t);
for(int i=0;i<n;++i)rec[t[i]].push_back(i+1);
sup=I(n);
Matrix tmp;
for(register int i=0;i<strlen(s);++i)
{
tmp=I(n);
for(int j=0;j<rec[s[i]].size();++j)
{
int pos=rec[s[i]][j];
tmp.a[pos][pos-1]=1;
}
sup=tmp*sup;
}
Ans.n=n,Ans.m=1,Ans.a[0][1]=1;
}
signed main()
{
pre();
Ans=power(sup,k)*Ans;
cout<<Ans.a[n][1];
return 0;
}