传送门：QAQQAQ
题意：给一个01矩阵A，他的相反矩阵为B，每一次变换都会将原矩阵面积乘4成为：
AB
BA
矩阵的左上角固定，变换无限次，现有q个询问，即求一个矩阵内的1的个数。
思路：因为反转，所以A，B矩阵拼起来刚好是一个全都为1的矩阵，所以答案就是匹配的A，B矩阵总点数/2和右下角1的个数之和
注意点：
1.因为数据较大，要用前缀和思想
2.要开longlong
3.注意询问时各个变量的重置
代码：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; int A[2001][2001],B[2001][2001],a[2002][2002],b[2002][2002]; int sa[2002][2002],sb[2002][2002]; ll n,m,q,t[33]; void init() { t[0]=1; for(int i=1;i<=30;i++) t[i]=t[i-1]*2; memset(sa,0,sizeof(sa)); memset(sb,0,sizeof(sb)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { sa[i][j]=sa[i-1][j]+sa[i][j-1]-sa[i-1][j-1]+A[i][j]; sb[i][j]=sb[i-1][j]+sb[i][j-1]-sb[i-1][j-1]+B[i][j]; } } } int s=0; void judge(ll x)//even->A odd->B { for(int i=30;i>=0;i--) { if(t[i]<x) x-=t[i],s++; } } ll solve(ll x,ll y) { s=0; ll ret=0; if(x==0||y==0) return 0; ret+=(x*y-(x%(2*n))*(y%(2*m)))/2;//n,m写错 ll xx=x-x%(2*n)+1; ll yy=y-y%(2*m)+1; ll tx=(xx-1)/n+1; ll ty=(yy-1)/m+1; judge(tx); judge(ty); ll dx=x-xx+1,dy=y-yy+1; if(s%2==1) { if(dx<=n&&dy<=m) ret+=sb[dx][dy]; if(dx<=n&&dy>m) ret+=sa[dx][dy-m]+sb[dx][m]; if(dx>n&&dy<=m) ret+=sb[n][dy]+sa[dx-n][dy]; if(dx>n&&dy>m) ret+=sb[n][m]+sa[n][dy-m]+sa[dx-n][m]+sb[dx-n][dy-m]; } else { if(dx<=n&&dy<=m) ret+=sa[dx][dy]; if(dx<=n&&dy>m) ret+=sb[dx][dy-m]+sa[dx][m]; if(dx>n&&dy<=m) ret+=sa[n][dy]+sb[dx-n][dy]; if(dx>n&&dy>m) ret+=sa[n][m]+sb[n][dy-m]+sb[dx-n][m]+sa[dx-n][dy-m]; } return ret; } int main() { scanf("%lld%lld%lld",&n,&m,&q); for(int i=1;i<=n;i++) { char str[1001]; scanf("%s",str+1); for(int j=1;j<=m;j++) { A[i][j]=str[j]-'0'; B[i][j]=(str[j]-'0')^1; } } init(); while(q--) { ll x1,y1,x2,y2;//开ll scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);//s不在这里重置 ll ans=solve(x2,y2)-solve(x1-1,y2)-solve(x2,y1-1)+solve(x1-1,y1-1); printf("%lld ",ans); } }