自动搬运

查看原文

来自洛谷，原作者为

	tobie 退役。

搬运于2025-08-24 23:05:55，当前版本为作者最后更新于2024-11-10 23:36:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

想题五分钟，调试两年半，码力有待加强。

首先把所有一定不可能匹配的括号串扔掉，他们没有用。

不妨设 $n,m$ 同阶，所有字符串的总长度为 $L$

对于原问题，考虑拆贡献：枚举每一对 $(i,j)$ ，求出有多少个合法括号串满足 $S_i$ 为前缀，$T_i$ 为后缀。

对 $|S|+|T|$ 和 $K$ 的大小关系分类讨论一下。

先考虑 $|S|+|T|>K$ 的部分，这意味着 $S$ 和 $T$ 在最终的序列中存在重叠部分。

考虑枚举 $S$ 和重叠部分长度 $d$，则根据 $|T|+|S|-d=k$ 可以知道 $T$ 的两个限制：

1. 长度为一个定值 $l$。
2. $T$ 的长度为 $d$ 的前缀和 $S$ 的长度为 $d$ 的后缀相同。
3. $T$ 的左右括号数量之差为 $\delta$。

判断字符串是否相等可以使用字符串哈希。接下来我们枚举所有长度和 $\delta$ 满足条件的串 $T$，转化为查询 $T$ 的前缀的哈希值在刚刚出现了几次，可以再开一个哈希表维护。

因为所有字符串的长度之和是 $L$，所以这部分的枚举量是 $O(L)$ 的，常数较小。

方便起见，以下记 $k=\frac k 2$，即左括号数量。

接下来是 $|S|+|T|\le K$。这说明 $S$ 和 $T$ 中间存在一段空缺。

根据经典套路，将括号串转化为一个 $(0,0)\to (k,k)$ 并且不碰到 $y=x+1$ 直线的路径。则这个路径的开头和结尾部分已知，则开头走到了 $(s_x,s_y)$，结尾走到了 $(e_x,e_y)$。

将坐标稍微平移一下，则我们需要解决如下问题：

记 $f(i,j)$ 表示 $(ax_i,ay_i)$ 走到 $(bx_j,by_j)$ 并且不经过 $y=x$ 的路径数量。你需要求出所有 $i,j$ 的 $f(i,j)$ 的和。

再次根据经典转化，我们将经过 $y=x$ 的路径，和到达 $(by,bx)$ 的路径建立一个双射。则答案可以转化成两个组合数相减的形式，可以再次拆开。

所以我们再次将问题转化为：

记 $g(i,j)$ 表示 $(ax_i,ay_i)$ 走到 $(bx_j,by_j)$ 的路径数量。你需要求出所有 $i,j$ 的 $g(i,j)$ 的和。

Lemma：最多有 $O(L^{\frac 2 3})$ 个本质不同的点。

注意到 $L=\sum (ax_i+ay_i)$ 的限制，取 $B=L^{\frac 1 3}$。

若 $ax+ay\le B$，则有 $O(B^2)$ 个小点。

若 $ax+ay>B$ 则最多只有 $O(\frac L B)$ 个大点。

综上，点数为 $O(B^2+\frac L B)=O(L^{\frac 2 3})$。

所以暴力枚举计算贡献就可以做到 $O(L^{\frac 4 3})$，但是对于赛后 vp 玩家来说还不够。

大点之间肯定没办法继续优化，考虑优化小点的计算过程。

再次联想到 AGC001E。我们发现，对于值域较小的情况，直接用 dp 就可以让复杂度和点数无关。

所以对于小点到小点的情况，我们可以把所有小点先走到 $x+y=B$ 和 $x+y=k-B$ 上，而这两条直线上分别只有 $O(B)$ 个点，就可以直接 $O(B^2)$ 统计答案。

对于大点到小点的情况，考虑对大点在 $x+y=B$ 直线的哪个部分分类讨论：如果 $bx+by\le B$，则我们可以使用刚才的 $dp$ 数组直接计算答案，否则继续枚举 $x+y=B$ 上的点计算贡献。

总时间复杂度为 $O(B^2+\frac {L^2} {B^2}+B\times \frac L B)=O(L)$，可能需要特别处理 $k\le B$ 的情况，细节较多。

（小声BB）这种题评紫是不是有点过于先进了？

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+9,M=1e6+9,mod=1e9+7;
namespace io{

inline void gi(int &x)
{
	x=0;char ch=getchar();
	while(ch<'0'||'9'<ch) ch=getchar();
	while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
void print(int x)
{
	if(x<=9) return putchar(x+'0'),void();
	print(x/10),putchar(x%10+'0');
}
inline void gstr(string &s)
{
	s.clear();
	char ch=getchar();
	if(ch!='('&&ch!=')') ch=getchar();
	while(ch=='('||ch==')') s.push_back(ch),ch=getchar();
}

}using io::gi;using io::print;using io::gstr;

void Add(int &x,int y){x+=y;if(x>=mod) x-=mod;}
int n,m,K,ans=0;
string S[N],T[N];
void readIn()
{
	gi(n);gi(m);gi(K);
	int n0=0,m0=0;
	for(int i=1;i<=n;i++)
	{
		gstr(S[++n0]);
		if(S[n0].size()>K){n0--;continue;}
		int cnt=0,cnt0=0,cnt1=0;
		for(int j=0;j<S[n0].size();j++)
		if(S[n0][j]=='(') cnt++,cnt0++;
		else if(!cnt){n0--;break;}
		else cnt--,cnt1++;
		if(cnt0*2>K||cnt1*2>K) n0--;
	}
	for(int i=1;i<=m;i++)
	{
		gstr(T[++m0]);
		if(T[m0].size()>K){m0--;continue;}
		int cnt=0,cnt0=0,cnt1=0;
		for(int j=T[m0].size()-1;j>=0;j--)
		if(T[m0][j]==')') cnt++,cnt0++;
		else if(!cnt){m0--;break;}
		else cnt--,cnt1++;
		if(cnt0*2>K||cnt1*2>K) m0--;		
	}
	n=n0,m=m0;
}

int fac[M],inv[M],ifac[M];
void ycl(int lim=1e6)
{
	fac[0]=fac[1]=inv[0]=inv[1]=ifac[0]=ifac[1]=1;
	for(int i=2;i<=lim;i++)
	{
		fac[i]=1ll*fac[i-1]*i%mod;
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
		ifac[i]=1ll*ifac[i-1]*inv[i]%mod;
	}
}
inline int C(int x,int y){return x>=y&&y>=0?1ll*fac[x]*ifac[y]%mod*ifac[x-y]%mod:0;}

namespace tobie{

const int Base=3;
int pw[M];
vector<int> hsh_S[N],hsh_T[N];
vector<int> id_S[M],id_T[M];
vector<int> sum_S[N];
int sum_T[N];
typedef pair<int,int> pii;
struct Node{
	pii key;
	int val,nxt;
}a[N];
int head[M],node_cnt=0;
inline int hsh2(pii num){return (1ll*num.first*(n+1)+num.second)%1000003;}
void Clear()
{
	for(int i=1;i<=node_cnt;i++) head[hsh2(a[i].key)]=0;
	node_cnt=0;
}
void Ins(pii key,int val)
{
	int h=hsh2(key);
	bool pd=0;
	for(int i=head[h];i;i=a[i].nxt)
	if(a[i].key==key)
	{
		pd=1;
		a[i].val+=val;
		break;
	}
	if(!pd)
	{
		node_cnt++;
		a[node_cnt].key=key;
		a[node_cnt].val=val;
		a[node_cnt].nxt=head[h];
		head[h]=node_cnt;
	}
}
int Qry(pii key)
{
	for(int i=head[hsh2(key)];i;i=a[i].nxt)
	if(a[i].key==key) return a[i].val;
	return 0;
}
void chkmx(int &x,int y){if(y>x) x=y;}
int nxt[N];
void work()
{
	pw[0]=1;
	for(int i=1;i<=K;i++) pw[i]=1ll*pw[i-1]*Base%mod;
	int mxlen_A=0,mxlen_B=0;
	for(int i=1;i<=n;i++)
	{
		chkmx(mxlen_A,S[i].size());
		id_S[S[i].size()].push_back(i);
	}
	for(int i=1;i<=m;i++)
	{
		chkmx(mxlen_B,T[i].size());
		id_T[T[i].size()].push_back(i);
	}
	for(int i=1;i<=n;i++)
	{
		int siz=S[i].size();
		hsh_S[i].resize(siz);
		hsh_S[i][0]=(S[i][siz-1]=='('?1:2);
		for(int j=1;j<siz;j++)
		hsh_S[i][j]=(hsh_S[i][j-1]+1ll*pw[j]*(S[i][siz-j-1]=='('?1:2)%mod)%mod;
		sum_S[i].resize(siz);
		sum_S[i][0]=(S[i][0]=='('?1:-1);
		for(int j=1;j<siz;j++)
		sum_S[i][j]=sum_S[i][j-1]+(S[i][j]=='('?1:-1);
	}
	for(int i=1;i<=m;i++)
	{
		int siz=T[i].size();
		hsh_T[i].resize(siz);
		hsh_T[i][0]=(T[i][0]=='('?1:2);
		for(int j=1;j<siz;j++)
		hsh_T[i][j]=(1ll*hsh_T[i][j-1]*Base%mod+(T[i][j]=='('?1:2))%mod;
		for(int j=0;j<siz;j++) sum_T[i]+=(T[i][j]==')'?1:-1);
	}
	nxt[mxlen_A]=mxlen_A+1;
	for(int i=mxlen_A-1;i>=1;i--)
	{
		if(id_S[i+1].size()) nxt[i]=i+1;
		else nxt[i]=nxt[i+1];
	}
//	cerr<<mxlen_A<<" "<<mxlen_B<<endl;
	int st=1;
	for(int d=1;d<=mxlen_A;d++)
	{
		while(st<d) st=nxt[st];
		for(int lenA=st;lenA<=mxlen_A;lenA=nxt[lenA])
		{
			int lenB=K-lenA+d;
			if(lenB>mxlen_B) continue;
			if(!id_S[lenA].size()||!id_T[lenB].size()) continue;
			Clear();
			for(int id:id_S[lenA]) Ins(make_pair(hsh_S[id][d-1],lenA==d?0:sum_S[id][lenA-d-1]),1);
			for(int id:id_T[lenB]) Add(ans,Qry(make_pair(hsh_T[id][d-1],sum_T[id])));
		}
	}
}

}
namespace eibot{

const int B0=3200;
struct Point{
	int x,y,v;
}a[N],b[N<<1];
int dp1[B0+10][B0+10],dp2[B0+10][B0+10];
inline int js(int x1,int y1,int x2,int y2){return C(x2-x1+y2-y1,x2-x1);}
vector<int> fz1,fz2;
void work()
{
	for(int i=1;i<=n;i++)
	{
		int cnt1=0,cnt2=0;
		for(int j=0;j<S[i].size();j++)
		if(S[i][j]=='(') cnt1++;
		else cnt2++;
		a[i]={cnt1+1,cnt2,1};
	}
	for(int i=1;i<=m;i++)
	{
		int cnt1=K/2,cnt2=K/2;
		for(int j=0;j<T[i].size();j++)
		if(T[i][j]=='(') cnt1--;
		else cnt2--;
		b[i]={cnt1+1,cnt2,1};
		b[m+i]={cnt2,cnt1+1,-1};
	}
	int k=K/2+1;
	int B=min(3200ll,k-1);
	for(int i=1;i<=n;i++)
	if(a[i].x+a[i].y<=B) dp1[a[i].x][a[i].y]++;
	for(int i=1;i<=m+m;i++)
	if(b[i].x+b[i].y>=k+k-B) Add(dp2[k-b[i].x][k-b[i].y],(mod+b[i].v)%mod);
	for(int i=0;i<=B;i++)
	for(int j=0;j<=B;j++)
	{
		if(i) Add(dp1[i][j],dp1[i-1][j]),Add(dp2[i][j],dp2[i-1][j]);
		if(j) Add(dp1[i][j],dp1[i][j-1]),Add(dp2[i][j],dp2[i][j-1]);
	}
	if(k<=B)
	{
		for(int i=1;i<=m;i++) Add(ans,dp1[b[i].x][b[i].y]);
		for(int i=m+1;i<=m+m;i++) Add(ans,mod-dp1[b[i].x][b[i].y]);
	}
	else
	{
		for(int i=0;i<=B;i++)
		for(int j=0;j<=B;j++)
		Add(ans,1ll*dp1[i][B-i]*dp2[j][B-j]%mod*js(i,B-i,k-j,k-B+j)%mod);
		for(int i=1;i<=n;i++)
		if(a[i].x+a[i].y>B)
		{
			fz1.push_back(i);
			if(a[i].x+a[i].y>=k+k-B) Add(ans,dp2[k-a[i].x][k-a[i].y]);
			else for(int j=0;j<=B;j++) Add(ans,1ll*dp2[j][B-j]*js(a[i].x,a[i].y,k-j,k-B+j)%mod);
		}
		for(int i=1;i<=m+m;i++)
		if(b[i].x+b[i].y<k+k-B)
		{
			fz2.push_back(i);
			int v=(b[i].v+mod)%mod;
			if(b[i].x+b[i].y<=B) Add(ans,1ll*dp1[b[i].x][b[i].y]*v%mod);
			else for(int j=0;j<=B;j++) Add(ans,1ll*dp1[j][B-j]*js(j,B-j,b[i].x,b[i].y)%mod*v%mod);
		}
		for(int x:fz1)
		for(int y:fz2)
		{
			int v=(b[y].v+mod)%mod;
			Add(ans,1ll*js(a[x].x,a[x].y,b[y].x,b[y].y)*v%mod);
		}
	}
}

}
signed main()
{
	int id__;
	scanf("%d",&id__);
	readIn();
	ycl();
	tobie::work();
	eibot::work();
	print(ans);
}