（2:00）OID：“完了，蓝屏了！”（代码全消失）
众人欢呼
OID：开机，“原题测试……“
（30min later）OID 开始传统艺能： “

∗

∗

∗

***

∗∗∗又AK了，承认自己强很难吗？……狗把人吃！……”
众人大汗，感到不妙……

众所周知，如果一个选手在比赛时提前码完了，AK 了，他就会觉得这场比赛简单，推己及人，觉得别人都 AK 了，于是自以为揭破真相似的对别人说：“你 AK 了”，这是传统艺能。因此，大多私人模拟赛都建议“AK 了不要大声喧哗”，顺便，如果见到有选手放骚话，搞传统艺能，那么你可以放心的认为ta AK 了。

是的，即便是开考两个小时后丢失所有代码，OID 还是不可阻挡地 AK 了。

而此时，我才看到这道题：

题面

给定一个由’A’,‘B’,'C’三种字母组成的字符串，你需要支持两种操作：

1 p c ：将位置

p

p

p 上的字符改为

c

c

c，其中

c

c

c 为’A’,‘B’,'C’其中之一，有可能该位置的字符没有变化。
2 l r ：求出子串
[

l

,

r

]

[l,r]

[l,r] 的本质不同子序列个数（不含空子序列）。

串

s 是串

t 的子序列当且仅当串

s 可以通过删去

t 中的某些字符得到。

两个子序列本质不同当且仅当它们长度不同或存在一个位置使得该位置上两个子序列的字符不同。

字符串长度

n ，操作数

m ，

≤

n,m\leq10^5

n,m≤105 。

题解

初看到这道题可能会感到无力，毕竟条件给得太复杂了。

我们可以先想想平方做法。

如果只是给你一个串，让你求本质不同的子序列个数（字符集很小），你会怎么做？

我们会用子序列自动机 ！子序列自动机的任意一条从源点出发的路径都可以唯一标识一个子序列。所以，我们把子序列自动机建出来，再求路径个数。

子序列自动机的构造方法很简单，每个位置继承右边位置的所有邻接点后，再把右边相邻点拿去替换某个邻接点。单次时间复杂度

(

∣

⋅

∣

)

O(|S|\cdot|\Sigma|)

O(∣S∣⋅∣Σ∣) ，考虑这道题的字符集大小是 3，总时间复杂度近似

(

)

O(nm)

O(nm) 。

接下来从子序列自动机的构造上着手优化。不少人应该意识到了，子序列自动机的构造非常简洁单调，非常傻，而且我们只需要路径个数，路径个数又是建自动机的过程中就可以求出来的——我们甚至没必要存下这个自动机。

所以经过深思熟虑，我们可以用矩阵乘法来标准化这一过程！

具体地，我们本来维护邻接点，但是实际上邻接点是谁不重要，我们只需要知道该邻接点出发的路径个数，即当前点走 A、B、C 分别能走到的路径个数。

我们令这三个值分别为

dp_A,dp_B,dp_C

dpA,dpB,dpC ，放到一个矩阵里：

[

]

\left[\begin{matrix} dp_A\\ dp_B\\ dp_C\\ \end{matrix}\right]

⎣⎡dpAdpBdpC⎦⎤ 。

当前点的转移非常傻，假如它是 A ，那么就会令

′

dp'_A=dp_A+dp_B+dp_C+1

dpA′=dpA+dpB+dpC+1，其余不变。为了方便，我们添上一个齐次项 1，那么转移就是这样：

[

]

[

]

[

′

]

\left[\begin{matrix} 1&1&1&1\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ \end{matrix}\right] \times \left[\begin{matrix} dp_A\\ dp_B\\ dp_C\\ 1 \end{matrix}\right] =\left[\begin{matrix} dp'_A\\ dp'_B\\ dp'_C\\ 1 \end{matrix}\right]

⎣⎢⎢⎡1000110010101001⎦⎥⎥⎤×⎣⎢⎢⎡dpAdpBdpC1⎦⎥⎥⎤=⎣⎢⎢⎡dpA′dpB′dpC′1⎦⎥⎥⎤

B 和 C 是类似的。

然后我们就可以把矩阵放到线段树上，维护区间乘积。时间复杂度

(

log

⁡

)

O(n\log n)

O(nlogn)，常数 64 。

CODE

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<vector>

#include<bitset>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 100005

#define LL long long

#define DB double

#define lowbit(x) (-(x) & (x))

#define ENDL putchar('\n')

#define FI first

#define SE second

//#pragma GCC optimize(2)

int xchar() {

	static const int maxn = 100000;

	static char b[maxn];

	static int len = 0,pos = 0;

	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);

	if(pos == len) return -1;

	return b[pos ++];

}

//#define getchar() xchar()

LL read() {

    LL f=1,x=0;int s = getchar();

    while(s < '0' || s > '9') {if(s<0) return -1;if(s=='-')f = -f;s = getchar();}

    while(s >= '0' && s <= '9') {x=x*10+(s^48);s = getchar();}

    return f*x;

}

void putpos(LL x) {if(!x)return ;putpos(x/10);putchar('0'+(x%10));}

void putnum(LL x) {

    if(!x) {putchar('0');return ;}

    if(x<0) {putchar('-');x = -x;}

    return putpos(x);

}

void AIput(LL x,int c) {putnum(x);putchar(c);}

const int MOD = 998244353;

int n,m,s,o,k;

struct mat{

	int n,m;

	int s[4][4];

	mat(){n=m=4;memset(s,0,sizeof(s));}

	mat(int a,int b,int c) {

		n=a;m=b;memset(s,0,sizeof(s));

		for(int i = 0;i < n;i ++) s[i][i] = c;

	}

}nm1(4,4,1);

mat ts[3];

mat operator * (mat a,mat b) {

	mat c(a.n,b.m,0);

	for(int i = 0;i < c.n;i ++) {

		for(int k = 0;k < a.m;k ++) {

			if(a.s[i][k])

			for(int j = 0;j < c.m;j ++) {

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

				if(c.s[i][j] >= MOD) c.s[i][j] -= MOD;

			}

		}

	}return c;

}

char a[MAXN];

mat tre[MAXN<<2];

int M;

void maketree(int n) {

	M=1;while(M<n+2)M<<=1;

	for(int i = 1;i <= n;i ++) {

		tre[M+i] = ts[a[i]-'A'];

	}

	for(int i = M-1;i > 0;i --) tre[i] = tre[i<<1|1] * tre[i<<1];

}

void addtree(int x,char y) {

	tre[M+x] = ts[y-'A'];

	for(int s = (M+x)>>1;s>0;s >>= 1) tre[s] = tre[s<<1|1] * tre[s<<1];

	return ;

}

mat findtree(int l,int r) {

	mat ls = nm1,rs = nm1;

	if(l > r) return nm1;

	for(int s=M+l-1,t=M+r+1;(s>>1) != (t>>1);s >>= 1,t >>= 1) {

		if(!(s&1)) ls = tre[s^1] * ls;

		if(t & 1) rs = rs * tre[t^1];

	}return rs * ls;

}

int main() {

	freopen("string.in","r",stdin);

	freopen("string.out","w",stdout);

	ts[0] = ts[1] = ts[2] = nm1;

	for(int i = 0;i < 3;i ++) {

		for(int j = 0;j < 4;j ++) ts[i].s[j][i] = 1;

	}

	n = read(); m = read();

	scanf("%s",a + 1);

	maketree(n);

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

		k = read();

		if(k == 1) {

			s = read(); char cc[3];

			scanf("%s",cc);

			addtree(s,cc[0]);

		}

		else {

			s = read();o = read();

			mat tr = findtree(s,o),as(1,4,0);

			as.s[0][3] = 1;

			as = as * tr;

			int ans = (0ll+ as.s[0][0] + as.s[0][1] + as.s[0][2]) % MOD;

			AIput(ans,'\n');

		}

	}

	return 0;

}

巴特西

[NOI P模拟赛] 传统艺能（子序列自动机、矩阵乘法，线段树）

题面

题解

CODE

最新文章

热门文章