ABC331D Tile Pattern

原题

题目描述

有一个 10^9 乘 10^9的方格网格。让 (i,j)表示从上往下数第 (i+1)行、从左往右数第 (j+1) 列的方格

每个方格要么是黑色要么是白色。方格 (i,j)的颜色由字符 P[i mod N][j mod N]表示，其中B表示黑色，W表示白色。这里,a mod b表示a除以b的余数。

回答 Q个查询。

每个查询给出四个整数 A,B,C,D要求你找出以 (A,B)为左上角、(C,D)为右下角的矩形区域内包含的黑色方格数量。

题目思路

令f(x,y)为满足条件的黑色方格的个数,则所求的答案就是f(c+1,d+1)-f(a,d+1)-f(c+1,b)+f(a,b)。但是如直接计算肯定比较麻烦，可以利用他的一些性质。当x=8,y=7时，如右图所示，可以将其分解为A*(x/n)*(y/n)、B*(y/n)、C*(x/n),D。其中A=f(n,n),B=f(x%n，n),C=f(y%n,n),D=f(x%n,y%n)。即可以将其分解为f(n,n)*(x/n)*(y/n) + (y/n)*f(x%n,n) + (x/n)*f(n,y%n) + f(x%n,y%n)。最后f(1,1)~f(n,n)可以使用前缀和的方式快速求出。

#include<bits/stdc++.h> using namespace std; using LL=long long;//给long long去个别名LL const int N=1010; int n,q,h[N][N]; LL f(LL x,LL y){ if(x<=n&&y<=n){ return h[x][y]; } return f(n,n)*(x/n)*(y/n)+(x/n)*f(n,y%n)+(y/n)*f(x%n,n)+f(x%n,y%n); } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>q; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ char c; cin>>c; h[i][j]=(c=='B')+h[i-1][j]+h[i][j-1]-h[i-1][j-1]; } } //前缀和优化↑ while(q--){//处理q次查询 int a,b,c,d; cin>>a>>b>>c>>d; c++; d++; cout<<f(c,d)-f(a,d)-f(c,b)+f(a,b)<<"\n"; } return 0; }