2023NOIP A层联测16 数学题

本文主要是介绍2023NOIP A层联测16 数学题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

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

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

设 $T$ 的每个字符出现的位置为 $pos_1,pos_2,\dots,pos_m$ ，则该匹配的权值为 $\sum\limits_{i=1}^mA_{pos_i}$ 。

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

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

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

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

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

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

题解

首先，我们可以想到对于每个 $1\leq k\leq n$ ，我们可以用 $D P$ 求出每个 $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^2m)$ 的。

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

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

当 $i\leq mid$ 时， $f_{i,j}$ 和 $g_{i,j}$ 表示 $S$ 从 $mi d$ 往前匹配到 $i$ ， $T$ 从 $k$ 往前匹配到 $j + 1$ 时的权值和方案数
当 $i > mi d$ 时， $f_{i,j}$ 和 $g_{i,j}$ 表示 $S$ 从 $mi d + 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<bits/stdc++.h>
#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;
}