2023NOIP A层联测16 数学题

题目大意

给定一个长度为$n$的字符串$S$和一个长度为$m$的字符串$T$，两个字符串都由小写字母组成。

一个匹配指$T$作为一个子序列在$S$中出现。

设$T$的每个字符出现的位置为$po{s}_1,po{s}_2,\dots ,po{s}_m$，则该匹配的权值为$\sum _{i=1}^m{A}_{po{s}_i}$。

其中$A$为给定的长度为$n$的数组。

两个匹配视作不同当且仅当存在一个匹配的位置不同。

有$q$个询问，每次询问$S[l\dots r]$和$T$的所有匹配的权值和。

输出所有答案模$10^9+7$后的异或和。

$1\le n\le 2\times 10^5,1\le m\le 30,1\le q\le 10^6$

时间限制$2000s$，空间限制$256MB$

题解

首先，我们可以想到对于每个$1\le k\le n$，我们可以用$DP$求出每个$l=k$的询问$[l,r]$。设$f_{i,j}$和$g_{i,j}$分别表示$S$从$k$匹配到了$i$，$T$从$1$匹配到$j$时的权值和方案数，则转移式为

$$f_{i,j}=f_{i-1,j}+[S_i==T_j]\times (f_{i-1,j-1}+g_j\times A_i)$$

$$g_{i,j}=g_{i-1,j}+[S_i==T_j]\times g_{i-1,j-1}$$

这样的话，对于每个$k$都是$O(nm)$的，而$k$有$n$种取值，时间复杂度是$O(n^{2}m)$的。

我们考虑用类似整体二分的方法。先将答案离线下来，然后处理区间$[1,n]$。每次处理区间$[l,r]$时，设$mid$为区间的中点，则分别处理左右端点都在$[l,mid]$上的询问和左右端点都在$[mid+1,r]$上的询问，这两部分可以递归来求。然后，考虑如何处理左端点在$[l,mid]$上且右端点在$[mid+1,r]$上的询问。

对于一段区间$l,r$，我们枚举$0\le k\le m$，表示字符串$T$中第$1$个到第$k$个字符在区间$[l,mid]$上，第$k+1$个到第$m$个字符在区间$[mid+1,r]$上。那么，用与上面的$DP$类似的方法，只不过$f_{i,j}$和$g_{i,j}$的定义有所修改：

• 当$i\le mid$时，$f_{i,j}$和$g_{i,j}$表示$S$从$mid$往前匹配到$i$，$T$从$k$往前匹配到$j+1$时的权值和方案数
• 当$i>mid$时，$f_{i,j}$和$g_{i,j}$表示$S$从$mid+1$往后匹配到$i$，$T$从$k+1$往后匹配到$j-1$时的权值和方案数

这里为什么不能直接表示为从$k$匹配到$j$呢？因为这样的话，在设初始值的时候两个部分会相互影响。

那么，一个确定的$k$对询问$[l_1,r_1]$的答案的贡献就是

$$ans+=f_{l_1,0}\times g_{r_1,m+1}+g_{l_1,0}\times f_{r_1,m+1}$$

这样，问题就解决了。

时间复杂度为$O(nm\log n)$。

code

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include
#define rg register
using namespace std;
const int mod=1e9+7;
const int N=200000,M=30,Q=1000000;
int n,m,q,pt,a[N+5],f[M+5],g[M+5],sf[N+5],sg[N+5],ans[Q+5];
char s[N+5],t[M+5];
struct node{
	int l,r,id;
};
int rd(){
	int t=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9'){
		t=t*10+ch-'0';
		ch=getchar();
	}
	return t;
}
void solve(int l,int r,vector<node>v){
	if(!v.size()) return;
	if(l==r){
		if(m==1){
			for(rg int i=0;i<v.size();i++)
			ans[v[i].id]+=(s[l]==t[1]);
		}
		return;
	}
	int mid=l+r>>1;
	vector<node>v1,v2,v3;
	for(rg int i=0;i<v.size();i++){
		if(v[i].r<=mid) v1.push_back(v[i]);
		else if(v[i].l>mid) v2.push_back(v[i]);
		else v3.push_back(v[i]);
	}
	solve(l,mid,v1);solve(mid+1,r,v2);
	for(rg int k=0;k<=m;k++){
		for(rg int i=0;i<=m+1;i++) f[i]=g[i]=0;
		for(rg int i=l;i<=r;i++) sf[i]=sg[i]=0;
		g[k]=1;
		for(rg int i=mid;i>=l;i--){
			for(rg int j=1;j<=k;j++){
				if(s[i]==t[j]){
					f[j-1]=(f[j-1]+f[j]+1ll*g[j]*a[i])%mod;
					g[j-1]=(g[j-1]+g[j])%mod;
				}
			}
			sf[i]=f[0];sg[i]=g[0];
		}
		g[k+1]=1;
		for(rg int i=mid+1;i<=r;i++){
			for(rg int j=m;j>=k+1;j--){
				if(s[i]==t[j]){
					f[j+1]=(f[j+1]+f[j]+1ll*g[j]*a[i])%mod;
					g[j+1]=(g[j+1]+g[j])%mod;
				}
			}
			sf[i]=f[m+1];sg[i]=g[m+1];
		}
		for(rg int i=0;i<v3.size();i++){
			ans[v3[i].id]=(ans[v3[i].id]+
				1ll*sf[v3[i].l]*sg[v3[i].r]+1ll*sg[v3[i].l]*sf[v3[i].r])%mod;
		}
	}
}
int main()
{
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	n=rd();m=rd();q=rd();
	for(rg int i=1;i<=n;i++) a[i]=rd();
	scanf("%s",s+1);
	scanf("%s",t+1);
	vector<node>v;
	for(rg int i=1,l,r;i<=q;i++){
		l=rd();r=rd();
		v.push_back((node){l,r,i});
	}
	solve(1,n,v);
	for(rg int i=1;i<=q;i++) pt^=ans[i];
	printf("%d",pt);
	return 0;
}
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