8.27 T2 炫酷原神（dp+矩阵快速幂+ddp）

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141609749

<cplusoj.com/d/senior/p/SS240827B>

这道题时间够慢慢做还是能做的，至少思路是很顺的，就是系数太难调了

考虑一个朴素的dp， f[i][c][j][t]f[i][c][j][t] 表示考虑前 ii 个字符，文章末尾有 jj 个 cc ，当前剪贴板上是 tt 的概率。这个dp的转移时显然的，这样子复杂度是 O(n2q262)O(n^2q26^2)

ii 显然可以滚掉， jj 的处理是个经典套路，直接丢状态里就行，因为我们并不涉及期望的高次运算。

现在我们相当于在dp一个 g(c,t)g(c,t) ，我们直接dp复杂度是 O(nq262)O(nq26^2) ，像这种每次修改一个字符的题我们肯定是想ddp的，但是目前状态太大，我们考虑能不能搞掉一个26。

假设我们把 gg 数组看成一个方阵，我们重新看一下代码，我们发现其实我们只需要维护 gg 每一行的和、每一列的和、对角线上的每个值，我们就能够求到答案了。

写完之后在看你会理解它的组合意义：

  • 每一行的和：文末为 cc 的概率

  • 每一列的和：剪贴板为 cc 的概率

  • 对角线上的值：文末为 cc ，且剪切板也为 cc

而当我们把这份程序写好，然后整理一下，我们可以发现一个事实：每个字母的转移时独立

我们重新思考回题目，对于每个字母，只关心这个位置的字母是不是自己，所以肯定是独立的

因此对于每个字母我们都可以很轻松拿一个矩阵来维护，然后直接上线段树即可。复杂度是 O(53(n+q)log⁡n)O(5^3(n+q)\log n)

然而这样子会被卡常，然后你思考一下发现因为你开了26棵线段树，有些地方是完全没用被用掉的，你可以把线段树改成动态开点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
 #define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
 #define debag(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
#define mo 998244853
#define N 200010
int pw(int A, int b) {
	long long ans = 1, a = A; 
	while(b) {
		if(b & 1) ans *= a; 
		a *= a; b >>= 1; 
		ans %= mo; a %= mo; 
	}
	return (int)ans; 
}
int pw(int a) { return pw(a, mo - 2); }
int fac[N], inv[N], ifac[N]; 
void init(int n) {
	int i; 
	for(i = fac[0] = 1; i <= n; ++i) fac[i] = fac[i-1] * i % mo; 
	ifac[n] = pw(fac[n], mo-2); 
	for(i = n - 1; i >= 0; --i) ifac[i] = ifac[i+1] * (i+1) % mo; 
    for(i = 1; i <= n; ++i) inv[i] = ifac[i] * fac[i-1] % mo; 
}
int C(int n, int m) {
	if(m > n) return 0;
	return fac[n] * ifac[m] % mo * ifac[n - m] % mo; 
}
inline void Mod(int &a) { if(a >= mo || a <= -mo) a %= mo; if(a < 0) a += mo; }
inline void Add(int &a, int b) { a += b; Mod(a); }
inline void Mul(int &a, int b) { Mod(b); a *= b; Mod(a); } 
const int iv2 = pw(2, mo - 2); 
const int iv3 = 1ll * iv2 * iv2 % mo; 
int n, m, i, j, k, T;
int ans, c, q, t, S; 
char s[N], str[5]; 
long long ys[5][5]; 

struct Martix {
	int a[5][5], i; 
	void clear() { memset(a, 0, sizeof(a)); }
	void init() { clear(); for(i = 0; i < 5; ++i) a[i][i] = 1; }
	int qans() { return a[2][4]; }
}Common, Supper, Com[N];

Martix operator * (Martix A, Martix B) {
	Martix C; int i, j, k; 
	for(i = 0; i < 5; ++i) for(j = 0; j < 5; ++j) ys[i][j] = 0; 
	for(i = 0; i < 5; ++i) 
		for(j = 0; j < 5; ++j)
			for(k = 0; k < 5; ++k)
				ys[i][k] += 1ll * A.a[i][j] * B.a[j][k]; 
	for(i = 0; i < 5; ++i) for(j = 0; j < 5; ++j) C.a[i][j] = ys[i][j] % mo; 
	return C; 
}


void init() {
	Common.clear(); 
	int a[5][5] = {
		{iv2, 0  , 0  , 0  , 0}, 
		{iv3, iv2, 0  , iv3, 0}, 
		{iv3, 0  , 1  , iv3, 0}, 
		{iv3, 0  , 0  , iv2, 0}, 
		{0  , 0  , 0  , 0  , 1}, 
	}; 
	memcpy(Common.a, a, sizeof(a)); 
	Supper.clear(); 
	int b[5][5] = {
		{iv2, 0        , 0  , 0  , iv2}, 
		{iv3, iv2 + iv3, 0  , iv3, iv3}, 
		{iv3, iv3      , 1  , iv3, iv3}, 
		{iv3, iv2      , 0  , iv2, iv3}, 
		{0  , 0        , 0  , 0  , 1  }, 
	}; 
	memcpy(Supper.a, b, sizeof(b)); 
}

#define M (1 << 23)

int ls[M], rs[M], tot; 
Martix a[M]; 

struct Segment_tree {
//#define ls (k << 1)
//#define rs (k << 1 | 1)
#define mid ((l + r) >> 1)
	void make_new(int &k, int l, int r) {
		k = ++tot; a[k] = Com[r - l + 1]; 
	}
	void push_up(int k) { a[k] = a[rs[k]] * a[ls[k]]; }
	void build(int &k, int l, int r){
		make_new(k, 1, n); 
		make_new(ls[k], 1, mid); 
		make_new(rs[k], mid + 1, r); 
	}
	void modify(int k, int l, int r, int x, int o) {
		if(l == r) {
			if(o == 0) a[k] = Common; 
			else a[k] = Supper; 
			return ; 
		}
		if(!ls[k]) make_new(ls[k], l, mid), make_new(rs[k], mid + 1, r); 
		if(x <= mid) modify(ls[k], l, mid, x, o); 
		else modify(rs[k], mid + 1, r, x, o); 
		push_up(k); 
	}
#undef ls
#undef rs
#undef mid
}Seg[26];

int rt[26]; 

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	init(); 
	n = read(); q = read(); 
	for(Com[0].init(), i = 1; i <= n; ++i) Com[i] = Common * Com[i - 1]; 
	scanf("%s", s + 1); for(i = 1; i <= n; ++i) s[i] -= 'a'; 
	for(i = 0; i < 26; ++i) Seg[i].build(rt[i], 1, n); 
	for(i = 1; i <= n; ++i) {
//		s[i] -= 'a'; 
		Seg[s[i]].modify(rt[s[i]], 1, n, i, 1); 
	}
	while(q--) {
		i = read(); scanf("%s", str); str[0] -= 'a'; 
		Seg[s[i]].modify(rt[s[i]], 1, n, i, 0); 
		Seg[str[0]].modify(rt[str[0]], 1, n, i, 1); 
		ans = 0; s[i] = str[0]; 
		for(i = 0; i < 26; ++i) {
			Add(ans, a[rt[i]].qans()); 
		}
		printf("%d\n", ans); 
	}
		
	return 0;
}