Description：

给一个字符串 $a$ ，每次询问如果删掉 $a$ 的第 $p$ 个字符，再给出一个字符 $c$ ，字符串 $c+a[p+1,n]+a[1,p-1]$ 的以 $x$ 结尾的本质不同子序列个数是多少。

$1\leqslant n,q\leqslant 200000,1\leqslant \Sigma\leqslant 200$

Solution：

设 $f[i]$ 表示以字符 $i$ 结尾的本质不同子序列个数，那么最后的答案就是 $f[x]$ ，转移为： $$ f[i]=sum-f[i]+1+f[i]=sum+1 $$ 其中 $sum=\sum f[i]$ 。

不难发现这个是一个线性变换，然后又观察题目给出的询问，不难发现是一个单个字符 $+$ 原串后缀 $+$ 原串前缀的形式，于是我们考虑一个暴力，预处理矩阵的前缀后缀积，然后每次就可以 $O(m^3)$ 把几部分乘起来回答询问，预处理是 $O(nm^3)$ 的，因此时间复杂度是 $O((n+q)m^3)$ 。

第一个优化：我们发现转移矩阵只有 $2m-1$ 个位置是有值的，于是我们可以只转移这些有值的位置，时间复杂度变成 $O(nm^2+qm^3)$ 。

第二个优化：我们发现最开始的向量只有 $m+1$ 处（提供常数的位置）有一个 $1$ ，经过了一次变换后 $c$ 这个位置也有了值，因此我们只要知道 $res[m+1][x]+res[c][x]$ 的值即可，假如我们求的是 $res[c][x]$ ，我们可以只枚举一个 $i$ ，然后对所有 $suf[c][i]\times pre[i][x]$ 求和，事件复杂度变为 $O(nm^2+qm)$ 。

第三个优化：观察预处理的矩乘式子，不难发现所有系数都是一，再观察一下会发现在求前缀积的时候实际上是把上一个复制过来，然后每次对上一个的某一行求和，加到新矩阵的一个列上，依次我们可以对每个矩阵开一个数组维护一下每行的和，然后用类似可持久化的思想除了发生变动的列其他的都沿用上一个矩阵的列，具体做法是可以开一个列的结构体的内存池，再求后缀积的时候，会发现实际上是一个复制上一个 $+$ 整行加，于是又可以可持久化 $+$ 整行打标记实现于是复杂度 $O((n+q)m)$ 可以通过。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,q;

#define MAXN 200010

int c[MAXN];

int s[MAXN];

#define MAXM 210

int f[MAXM],sum;

#define MOD 998244353

struct matrix

{

	int a[MAXM][MAXM];

	matrix(){memset(a,0,sizeof(a));}

	friend matrix operator * (matrix a,matrix b)

	{

		matrix c;

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

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

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

					c.a[i][j] = (c.a[i][j] + 1ll * a.a[i][k] * b.a[k][j] % MOD) % MOD;

		return c;

	}

}tr[MAXM];

int main()

{

	scanf("%d%d%d",&n,&m,&q);

	for(int i = 1;i <= n;++i)scanf("%d",&c[i]);

	int p,x,v;

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

	{

		for(int i = 1;i <= m;++i)tr[l].a[i][i] = 1;

		for(int i = 1;i <= m;++i)tr[l].a[i][l] = 1;

		tr[l].a[m + 1][l] = 1;tr[l].a[m + 1][m + 1] = 1;

	}

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

	{

		scanf("%d%d%d",&p,&x,&v);

		int tot = 0;

		s[++tot] = x;

		for(int k = p + 1;k <= n;++k)s[++tot] = c[k];

		for(int k = 1;k < p;++k)s[++tot] = c[k];

		matrix res = tr[x];

		for(int k = 2;k <= n;++k)res = res * tr[s[k]];

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

		{

			int sum = 0;

			for(int l = 1;l <= m;++l)sum = (sum + f[l]) % MOD;

			f[s[k]] = sum + 1;

		}

		cout << f[v] << " " << res.a[m + 1][v] << endl;

		for(int l = 1;l <= m;++l)f[l] = 0;

	}

	return 0;

}