2024.11.12 鮮花

P11270 【MX-S5-T4】魔法少女們

P11270 【MX-S5-T4】魔法少女們題解

這世界那么多人

這世界有那么多人
人群里 敞著一扇門
我迷朦的眼睛里長存
初見你藍色清晨
這世界有那么多人
多幸運 我有個我們
這悠長命運中的晨昏
常讓我 望遠方出神
灰樹葉飄轉在池塘
看飛機轟的一聲去遠鄉
光陰的長廊 腳步聲叫嚷
燈一亮 無人的空蕩
晚風中閃過 幾幀從前啊
飛馳中旋轉 已不見了嗎
遠光中走來 你一身晴朗
身旁那么多人 可世界不聲 不響
這世界有那么多人
多幸運 我有個我們
這悠長命運中的晨昏
常讓我 望遠方出神
灰樹葉飄轉在池塘
看飛機轟的一聲去遠鄉
光陰的長廊 腳步聲叫嚷
燈一亮 無人的空蕩
晚風中閃過 幾幀從前啊
飛馳中旋轉 已不見了嗎
遠光中走來 你一身晴朗
身旁那么多人 可世界不聲 不響
笑聲中浮過 幾張舊模樣
留在夢田里 永遠不散場
暖光中醒來 好多話要講
世界那么多人 可是它不聲 不響
這世界有那么個人
活在我 飛揚的青春
在淚水里浸濕過的長吻
常讓我 想啊想出神

最近都在寫多項式卷積，換換腦子，寫點一點也不清新的逆天題。

首先先去除不合法的 \(S,T\)，具體的就是不能通過在后面/前面加右/左括號變成合法括號序的。

考慮經典做法，設 ( 為 \(-1\)，) 為 \(1\)，設一個括號序 \(X\) 的值 \(V(X)\) 為其所有括號的值和。

首先我會暴力，考慮枚舉 \(S,T\) 分別做前后綴，統計個數。分討：\(|S|+|T|\le k\) 和 \(|S|+|K|>k\)，\(|S|+|K|>k\) 能成立當且僅當它們相交的部分相同，且拼成的括號序合法，因為前后綴分別合法，所以括號序合法等價于拼成的值為 \(0\)，維護 \(S,T\) 的 hash 和 \(V\) 的前綴輕松判。

\(|S|+|T|\le k\) 略微困難，考慮中間空余填法方案，其相當于是從 \(a \to b\)，每次 \(\pm 1\)，在任意時刻前綴和 \(\le 0\)，這是經典格路計數，可以直接上卡特蘭數/反射容斥，單次查詢可以做到 \(O(1)\)。

現在復雜度是 \(n^2\) 的，實現精細可以過 \(56pts\)，考慮優化。

\(|S|+|K|>k\) 依然比較簡單，考慮將后綴 hash，長度和 \(V\) 做成三元組扔進 hash 表，前綴直接查。

\(|S|+|T|\le k\) 考慮一個括號序的長度和值完全一樣顯然是沒有區別的，將它們扔進一個等價類一起算，題解說是 \(L^{\frac{2}{3}}\) 種等價類，不會正，但因為總長和單個長度的限制確實不會太多，于是有了 \(84pts\)。

考慮繼續優化 \(|S|+|T|\le k\)，發現對于 \((l,s)\) 的二元等價類，\(l\) 是長度，\(s\) 是值，顯然可以拆成 \((l+1,s+1),(l+1,s-1)\)，即考慮填上一個括號，于是根號分治，直接將 \(l<\sqrt L\) 的都推到 \(\sqrt L\)，顯然復雜度是 \(\mathcal{O}((\sqrt L)^2+(\sqrt L+\frac{L}{\sqrt L})^2)=\mathcal{O}(L)\)。

一些細節：\(|S|+|K|>k\) 需要卡場，可以枚舉斷點，這樣可以往 hash 表少扔幾個元素，實在不行手寫，\(|S|+|T|\le k\) 部分推到根號是要考慮有的前綴和后綴的匹配會被推成相交，在恰好接上時計算貢獻即可。閾值分治的閾值開小點跑的比較快，算 hash 和 \(V\) 的時候不建議用 vector，反正我的暴力改成拼多多（開一個大數組動態分配空間）直接 \(44pts\to 56pts\)。

Code

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define endl '\n'
#define Il __always_inline
#ifdef LOCAL
	FILE *InFile=freopen("in_out/in.in","r",stdin),*OutFile=freopen("in_out/out.out","w",stdout);
#else
    FILE *InFile=stdin,*OutFile=stdout;
#endif

const int N=2e5+3,M=5e5+3,S=1e7+3,HBs=2333,MOD=1e9+7;
int Add(int a,int b){return (a+=b)>=MOD?a-MOD:a;}
int Sub(int a,int b){return (a-=b)<0?a+MOD:a;}

int n,m,ck,ans,fac[M],ivf[M],mln; ull hpw[M];

namespace Node{
	ull chs[S+N<<1],*hp=chs; int csm[S+N<<1],*sp=csm;
	struct Nd{
		ull *hs; int *sm; int len,sum;
		Il void In(const string &s){
			len=s.size(); hs=hp,hp+=len+2,sm=sp,sp+=len+2; mln=max(mln,len);
			hs[0]=0,sm[0]=0,sum=0; int p=0; ull hsh=0;
			for(auto c:s) ++p,hs[p]=hsh=hsh*HBs+c,sm[p]=sum+=c=='('?1:-1;
		}
		Il int Sm()const{return sum;}
		Il ull Hs(int l,int r){return hs[r]-hs[l-1]*hpw[r-l+1];}
	};
}using Node::Nd;
Nd s[N],t[N]; int lns,lnt;

Il int C(int a,int b){return a<b||b<0?0:1ll*fac[a]*ivf[b]%MOD*ivf[a-b]%MOD;}
Il int P(int a,int b,int c,int d){return C(c-a+d-b,d-b);}
Il int Cat(int a,int b,int c,int d){return Sub(P(a,b,c,d),P(a,b,d-1,c+1));}
Il int Cnt(int x,int y,int l){int a=(y-x+l)>>1,b=(x-y+l)>>1; return a+b==l?Cat(x,0,x+a,b):0;}

Il bool Chkl(const string &a){
	int sum=0;
	for(auto c:a) if((sum+=c=='('?1:-1)<0) return 0;
	return 1;
}
Il bool Chkr(const string &a){
	int sum=0;
	for(auto c=a.rbegin();c!=a.rend();++c) if((sum+=*c==')'?1:-1)<0) return 0;
	return 1;
}

Il size_t Hash(const tuple<ull,int,int> &p){return get<0>(p)+hash<int>()(get<1>(p))*HBs^hash<int>()(get<2>(p));};
struct Map{
	static const int MMOD=10000019;
	struct O{tuple<ull,int,int> v; int w,t;}o[200050];
	int n,c,w,h[MMOD],p[200050];
	void Clr(){for(int i=1;i<=w;++i) h[p[i]]=0; c=w=0;}
	void Ins(const tuple<ull,int,int> &x){
		int u=Hash(x)%MMOD;
		for(int i=h[u];i;i=o[i].t) if(o[i].v==x) return ++o[i].w,void();
		o[++c]={x,1,h[u]},h[u]=c,p[++w]=u;
	}
	int Get(const tuple<ull,int,int> &x){
		int u=Hash(x)%MMOD;
		for(int i=h[u];i;i=o[i].t) if(o[i].v==x) return o[i].w;
		return 0;
	}
} mp;
Il void Slv1(){
	sort(s+1,s+lns+1,[](const Nd &a,const Nd &b){return a.len==b.len?a.Sm()<b.Sm():a.len>b.len;});
	sort(t+1,t+lnt+1,[](const Nd &a,const Nd &b){return a.len==b.len?a.Sm()<b.Sm():a.len>b.len;});
	for(int i=1;i<=ck;++i){
		mp.Clr();
		for(int j=1;j<=lnt;++j){
			if(t[j].len<i) break;
			mp.Ins({t[j].hs[i],-t[j].Sm(),ck-t[j].len});
		}
		for(int j=1;j<=lns;++j){
			if(s[j].len<i) break;
			int l=s[j].len,p=l-i;
			ans=Add(ans,mp.Get({s[j].Hs(p+1,l),s[j].sm[p],p}));
		}
	}
}

Il void Slv2(){
	map<pair<int,int>,int> cs,ct; int B=min({ck/2-1,600,mln});
	map<pair<int,int>,int> cv;
	for(int i=1;i<=lns;++i) ++cs[{s[i].len,s[i].Sm()}];
	for(int i=1;i<=lnt;++i) ++ct[{t[i].len,t[i].Sm()}];
	for(auto k=cs.begin();k!=cs.end();){
		int l=k->first.first,s=k->first.second,t=k->second;
		if(l>=B) break; if(ct.count({ck-l,-s})) ans=(ans+1ll*ct[{ck-l,-s}]*t%MOD)%MOD;
		(cs[{l+1,s+1}]+=t)%=MOD; if(s>0) (cs[{l+1,s-1}]+=t)%=MOD; k=cs.erase(k);
	}
	for(auto k=ct.begin();k!=ct.end();){
		int l=k->first.first,s=k->first.second,t=k->second;
		if(l>=B) break; if(cs.count({ck-l,-s})) ans=(ans+1ll*cs[{ck-l,-s}]*t%MOD)%MOD;
		if(s<0) (ct[{l+1,s+1}]+=t)%=MOD; (ct[{l+1,s-1}]+=t)%=MOD; k=ct.erase(k);
	}
	for(auto l:cs) for(auto r:ct){
		int ll=l.first.first,rl=r.first.first,ls=l.first.second,rs=r.first.second,lt=l.second,rt=r.second;
		if(ll+rl<=ck) ans=(ans+1ll*Cnt(ls,-rs,ck-ll-rl)*lt%MOD*rt)%MOD;
	}
}

int main(){
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	hpw[0]=1; for(int i=1;i<=M-3;++i) hpw[i]=hpw[i-1]*HBs;
	fac[0]=1; for(int i=1;i<=M-3;++i) fac[i]=1ll*fac[i-1]*i%MOD;
	ivf[M-3]=329292354; for(int i=M-3;i;--i) ivf[i-1]=1ll*ivf[i]*i%MOD;
	int cccc; cin>>cccc>>n>>m>>ck;
	for(int i=1;i<=n;++i){string a; cin>>a; if(Chkl(a)) s[++lns].In(a);}
	for(int i=1;i<=m;++i){string a; cin>>a; if(Chkr(a)) t[++lnt].In(a);}
	Slv1(); Slv2(); cout<<ans<<endl;
}

posted @ 2024-11-12 20:44 xrlong 閱讀(93) 評論(4) 收藏舉報

刷新頁面返回頂部

xrlong

博客密碼是 K8 色號

2024.11.12 鮮花

P11270 【MX-S5-T4】魔法少女們題解

公告

Loading

xrlong

博客密碼是 K8 色號

2024.11.12 鮮花

P11270 【MX-S5-T4】魔法少女們 題解

公告

Loading

P11270 【MX-S5-T4】魔法少女們題解