2023NOIP A层联测16 数学题

联测16 数学题"/>

2023NOIP A层联测16 数学题

题目大意

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

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

设 T T T的每个字符出现的位置为 p o s 1 , p o s 2 , … , p o s m pos_1,pos_2,\dots,pos_m pos1​,pos2​,…,posm​，则该匹配的权值为 ∑ i = 1 m A p o s i \sum\limits_{i=1}^mA_{pos_i} i=1∑m​Aposi​​。

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

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

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

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

1 ≤ n ≤ 2 × 1 0 5 , 1 ≤ m ≤ 30 , 1 ≤ q ≤ 1 0 6 1\leq n\leq 2\times 10^5,1\leq m\leq 30,1\leq q\leq 10^6 1≤n≤2×105,1≤m≤30,1≤q≤106

时间限制 2000 s 2000s 2000s，空间限制 256 M B 256MB 256MB

题解

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

f i , j = f i − 1 , j + [ S i = = T j ] × ( f i − 1 , j − 1 + g j × A i ) f_{i,j}=f_{i-1,j}+[S_i==T_j]\times(f_{i-1,j-1}+g_j\times A_i) fi,j​=fi−1,j​+[Si​==Tj​]×(fi−1,j−1​+gj​×Ai​)

g i , j = g i − 1 , j + [ S i = = T j ] × g i − 1 , j − 1 g_{i,j}=g_{i-1,j}+[S_i==T_j]\times g_{i-1,j-1} gi,j​=gi−1,j​+[Si​==Tj​]×gi−1,j−1​

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

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

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

• 当 i ≤ m i d i\leq mid i≤mid时， f i , j f_{i,j} fi,j​和 g i , j g_{i,j} gi,j​表示 S S S从 m i d mid mid往前匹配到 i i i， T T T从 k k k往前匹配到 j + 1 j+1 j+1时的权值和方案数
• 当 i > m i d i>mid i>mid时， f i , j f_{i,j} fi,j​和 g i , j g_{i,j} gi,j​表示 S S S从 m i d + 1 mid+1 mid+1往后匹配到 i i i， T T T从 k + 1 k+1 k+1往后匹配到 j − 1 j-1 j−1时的权值和方案数

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

那么，一个确定的 k k k对询问 [ l 1 , r 1 ] [l_1,r_1] [l1​,r1​]的答案的贡献就是

a n s + = f l 1 , 0 × g r 1 , m + 1 + g l 1 , 0 × f r 1 , m + 1 ans+=f_{l_1,0}\times g_{r_1,m+1}+g_{l_1,0}\times f_{r_1,m+1} ans+=fl1​,0​×gr1​,m+1​+gl1​,0​×fr1​,m+1​

这样，问题就解决了。

时间复杂度为 O ( n m log ⁡ n ) O(nm\log n) O(nmlogn)。

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;
}