题解：P11270 【MX-S5-T4】魔法少女们
想题五分钟，调试两年半，码力有待加强。
首先把所有一定不可能匹配的括号串扔掉，他们没有用。
不妨设
对于原问题，考虑拆贡献：枚举每一对
对
先考虑
考虑枚举
- 长度为一个定值
l 。 -
-
判断字符串是否相等可以使用字符串哈希。接下来我们枚举所有长度和
因为所有字符串的长度之和是
方便起见，以下记
接下来是
根据经典套路，将括号串转化为一个
将坐标稍微平移一下，则我们需要解决如下问题：
记
再次根据经典转化，我们将经过
所以我们再次将问题转化为：
记
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}) 。
所以暴力枚举计算贡献就可以做到
大点之间肯定没办法继续优化，考虑优化小点的计算过程。
再次联想到 AGC001E。我们发现，对于值域较小的情况，直接用 dp 就可以让复杂度和点数无关。
所以对于小点到小点的情况，我们可以把所有小点先走到
对于大点到小点的情况，考虑对大点在
总时间复杂度为
（小声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);
}