专栏文章

题解：P6350 [PA 2011] Laser Pool

__lbw_malerlee
P6350题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minshkdr
此快照首次捕获于
2025/12/02 07:37
3 个月前
此快照最后确认于
2025/12/02 07:37
3 个月前
查看原文
反弹考虑把网格翻转无穷遍就变成直线，而翻转两次相当于平移。
问题转化为给定 s,ts,t，每次询问 x,y,Lx,y,L 求：
∑i=0Ls(x+i) mod n∣t(y+i) mod m\sum_{i=0}^L s_{(x+i)\bmod n}|t_{(y+i)\bmod m}
那么我们先转化成求：
∑i=0Ls(x+i) mod n×t(y+i) mod m\sum_{i=0}^L s_{(x+i)\bmod n}\times t_{(y+i)\bmod m}
发现这个东西看起来很不可做，因为就算 n=mn=m 的情况都等价于卷积了。
而 n≠mn\not =m 的时候更不好操作，如果任意查询两个区间的对应位置乘法和只能分块 NTT。
那这题能不能规约到查询两个区间的对应位置乘法和呢？
我们考虑现在变量有 x,y,Lx,y,L，如果把 xx 移到 00 就好了，而这一步是查询区间对应位置乘法和。
剩下我们先假设 x=0,L=nx=0,L=n，那么 yy 只有 mm 种，把这些 x,y,Lx,y,L 的答案用一遍减法卷积预处理出来为 fyf_y（具体是先把第二个数组复制若干变，然后就是把第一个数组平移和第二个点乘，翻转就是卷积）。
那么查询可以不断把整段的 nn 跳过去，这一部分对于 yy 每次加上 nn 贡献 fyf_y，是一个环上的查询，前缀和一下就可以求出。
剩下还有一段也是区间对应位置乘法。
但是如果真的写了分块 NTT 可能有危险，然而注意到查询比较少，直接 bitset 就好啦！
时间复杂度 O(nqω+nlog⁡n)O(\dfrac{nq}{\omega}+n\log n)。
CPP
#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<queue>
#include<bitset>
#include<cstdio>
#include<vector>
#include<random>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
#define I ll
#define her1 20081214
#define IV void
#define cht 998244353
#define ld long double
#define Aestas16 392699
#define ull unsigned long long
#define cp(x,y)memcpy(x,y,sizeof y)
#define mem(x,val)memset(x,val,sizeof x)
#define D(i,j,n)for(register int i=j;i>=n;i--)
#define E(i,now)for(register int i=first[now];i;i=e[i].nxt)
#define F(i,j,n)for(register int i=j;i<=n;i++)
#define DL(i,j,n)for(register i64 i=j;i>=n;i--)
#define EL(i,now)for(register i64 i=first[now];i;i=e[i].nxt)
#define FL(i,j,n)for(register i64 i=j;i<=n;i++)
//#define D(i,j,n)for(int i=j;i>=n;i--)
//#define E(i,now)for(int i=first[now];i;i=e[i].nxt)
//#define F(i,j,n)for(int i=j;i<=n;i++)
//#define DL(i,j,n)for(register ll i=j;i>=n;i--)
//#define EL(i,now)for(register ll i=first[now];i;i=e[i].nxt)
//#define FL(i,j,n)for(register ll i=j;i<=n;i++)
ll read(){
	ll ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')ans=ans*10+c-'0',c=getchar();
	return ans*f;
}
#undef ll
#include "assert.h"
mt19937_64 rnd(her1);
#include "functional"
using i64 = long long;
const int maxn = 2e5+5;

bitset<maxn*2>b1,b2,all;bool fg=0;char s[maxn],t[maxn];
i64 n,m,q,X[maxn],Y[maxn],vx[maxn],vy[maxn],L[maxn],Ans[maxn];
i64 calc(i64 x,i64 y){return(b1>>x&b2>>y).count();}

vector<i64>s1[maxn],V[maxn];bool vis[maxn];
i64 sum[maxn],idx[maxn],idy[maxn];

#define G 3
i64 rev[(1<<20)+5],f[(1<<20)+5],g[(1<<20)+5];
i64 qpow(i64 n,i64 base=cht-2){
	i64 ans=1;
	while(base){
		if(base&1)ans=ans*n%cht;
		n=n*n%cht;base>>=1;
	}
	return ans;
}
IV NTT(i64*a,i64 limit,bool tp){
	i64 sb=__lg(limit);
	F(i,0,limit-1)rev[i]=(rev[i>>1]>>1|((i&1)<<sb-1));
	F(i,0,limit-1)if(i<rev[i])swap(a[i],a[rev[i]]);
	for(int p=2;p<=limit;p<<=1){
		i64 k=(p>>1),wG=qpow(G,(cht-1)/p);
		for(int l=0,w=1;l<limit;l+=p,w=1)
			F(i,l,l+k-1){
				i64 x=a[i],y=a[i+k]*w%cht;
				a[i]=(x+y)%cht;a[i+k]=(x-y+cht)%cht;
				w=w*wG%cht;
			}
	}
	if(tp==1){
		i64 inv=qpow(limit);
		F(i,0,limit-1)a[i]=a[i]*inv%cht;
		reverse(a+1,a+limit);
	}
}
IV solve(i64 r){
	if(r==-1){
		reverse(t,t+m);
	}
	F(i,0,2*maxn-1)all[i]=1;
	F(i,0,n-1)b1[i]=!(s[i]-'0');
	F(i,0,2*m-1)b2[i]=!(t[i%m]-'0');

	F(i,0,m-1)vis[i]=0;
	i64 limit=1;
	while(limit<=n+2*m)limit<<=1;
	F(i,0,limit-1)f[i]=g[i]=0;
	F(i,0,n-1)f[i]=b1[n-1-i];
	F(i,0,2*m-1)g[i]=b2[i];
	NTT(f,limit,0);NTT(g,limit,0);
	F(i,0,limit-1)f[i]=f[i]*g[i]%cht;
	NTT(f,limit,1);
	F(i,0,m-1)sum[i]=(f[i+n-1]+cht)%cht;
	i64 cc=0;
	F(i,0,m-1)if(!vis[i]){
		i64 now=i;cc++;V[cc].clear();
		while(!vis[now]){
			idx[now]=cc;idy[now]=V[cc].size();
			V[cc].push_back(sum[now]);vis[now]=1;now=(now+n)%m;
		}
		s1[cc]=V[cc];
		F(z,1,(i64)s1[cc].size()-1)s1[cc][z]+=s1[cc][z-1];
	}
	F(i,1,q)if(vy[i]==r){
		vy[i]=1;
		if(r==-1)Y[i]=m-1-Y[i];
		auto ck=[&](){return s[X[i]]=='0'&&t[Y[i]]=='0';};

		if(L[i]<n-X[i]){
			Ans[i]-=(all>>2*maxn-L[i]-1&b1>>X[i]&b2>>Y[i]).count();
			continue;
		}
		Ans[i]-=calc(X[i],Y[i]);
		Y[i]=(Y[i]+n-X[i])%m;L[i]-=n-X[i];X[i]=0;
		i64 k=L[i]/n;L[i]%=n;
		{
			i64 a=idx[Y[i]],b=idy[Y[i]];
			if(k>=s1[a].size()){
				Ans[i]-=(k/s1[a].size())*s1[a].back();
				k%=s1[a].size();
			}
			if(b+k<s1[a].size()){
				if(k)Ans[i]-=(s1[a][b+k-1]-(b?s1[a][b-1]:0));
			}
			else if(k){
				Ans[i]-=(s1[a].back()-(b?s1[a][b-1]:0));
				if(b+k-1>=V[a].size()){
					Ans[i]-=s1[a][b+k-1-(i64)V[a].size()];
				}
			}
			if(k>=0)Y[i]=(Y[i]+n*k)%m;
		}
		

		Ans[i]-=(all>>2*maxn-L[i]-1&b1&b2>>Y[i]).count();
	}
}
int main(){
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	
	n=read();m=read();
	scanf("%s%s",s,t);i64 rn=n,rm=m;
	D(i,rn-2,1)s[n++]=s[i];
	D(i,rm-2,1)t[m++]=t[i];
	if(n>m)swap(n,m),swap(s,t),fg=1;

	q=read();
	F(i,1,q){
		Y[i]=read()-1;X[i]=read()-1;vy[i]=read();vx[i]=read();L[i]=read();
		Ans[i]=L[i]+1;
		if(fg){
			swap(X[i],Y[i]);swap(vx[i],vy[i]);
		}
		if(vx[i]==-1){
			X[i]=(X[i]+vx[i]*L[i]%n+n)%n;
			Y[i]=(Y[i]+vy[i]*L[i]%m+m)%m;
			vx[i]=-vx[i];vy[i]=-vy[i];
		}
	}
	solve(1);solve(-1);
	F(i,1,q)printf("%lld\n",Ans[i]);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...