题解：P6350 [PA 2011] Laser Pool

· · 题解

反弹考虑把网格翻转无穷遍就变成直线，而翻转两次相当于平移。

问题转化为给定 s,t，每次询问 x,y,L 求：

\sum_{i=0}^L s_{(x+i)\bmod n}|t_{(y+i)\bmod m}

那么我们先转化成求：

\sum_{i=0}^L s_{(x+i)\bmod n}\times t_{(y+i)\bmod m}

发现这个东西看起来很不可做，因为就算 n=m 的情况都等价于卷积了。

而 n\not =m 的时候更不好操作，如果任意查询两个区间的对应位置乘法和只能分块 NTT。

那这题能不能规约到查询两个区间的对应位置乘法和呢？

我们考虑现在变量有 x,y,L，如果把 x 移到 0 就好了，而这一步是查询区间对应位置乘法和。

剩下我们先假设 x=0,L=n，那么 y 只有 m 种，把这些 x,y,L 的答案用一遍减法卷积预处理出来为 f_y（具体是先把第二个数组复制若干变，然后就是把第一个数组平移和第二个点乘，翻转就是卷积）。

那么查询可以不断把整段的 n 跳过去，这一部分对于 y 每次加上 n 贡献 f_y，是一个环上的查询，前缀和一下就可以求出。

剩下还有一段也是区间对应位置乘法。

但是如果真的写了分块 NTT 可能有危险，然而注意到查询比较少，直接 bitset 就好啦！

时间复杂度 O(\dfrac{nq}{\omega}+n\log n)。

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