自动搬运

查看原文

来自洛谷，原作者为

	whileAK **

搬运于2025-08-24 22:33:23，当前版本为作者最后更新于2024-08-16 17:17:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P7819 [RC-05] Xor Matrix

思路

$k$ 进制下的异或每一位都是独立的。考虑枚举每一位 $p$，这位的贡献就是矩形内所有数的第 $p$ 位数字之和再对 $k$ 取模，最后乘上 $k^p$。对于以 $(x,y)$ 为左上角，$(z,w)$ 为右下角的矩形，可以用容斥把左上角改成 $(1,1)$，则第 $p$ 位的答案是:

$$\sum_{i=1}^{z}\sum_{j=1}^{w} \lfloor \frac{(i-1)m+j}{k^p}\rfloor $$

对 $k$ 取模。上式相当于：

$$\sum_{i=1}^{z}\sum_{j=0}^{w-1} \lfloor \frac{j+(i-1)m+1}{k^p}\rfloor $$

这样第二个循环就可以用类欧 $O(1)$ 算。不会类欧的可以点这里。这样我们只用枚举 $i$，总复杂度 $O(qn\log{V})$。

然而 $n$ 可能很大，能达到 $10^{10}$，但 $nm$ 也才 $10^{10}$，当 $n$ 很大时 $m$ 很小。我们想再推一个枚举 $m$ 的式子，在 $n$ 很大时枚举 $m$。只要交换求和符号就好了：

$$\sum_{j=1}^{w}\sum_{i=0}^{z-1} \lfloor \frac{im+j}{k^p}\rfloor $$

也可以用类欧做，但算第二个式子需要 $O(\log{n})$ 而不是 $O(1)$。所以总复杂度 $O(q\min{(n,m)}\log{V}\log{n})$。

注意

1、本题卡常，请适当使用卡常技巧。注意第一种情况复杂度优于第二种情况，第一种情况可以在 $z\le10^6$ 时用，第二种情况可以在 $w\le10^4$ 时用。

2、类欧中有需要除以 $2$ 的式子，由于模数 $k$ 没有限制，所以不一定有逆元，需要特殊处理。

3、全部开 long long，必要时开 __int128，计算过程中可能爆 long long。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void rd(int &p){
	p=0;int f(0);char z=getchar();
	while(z>'9'||z<'0'){if(z=='-')f^=1;z=getchar();}
	while(z>='0'&&z<='9')p=(p<<1)+(p<<3)+z-'0',z=getchar();
	if(f)p=-p;
}
void rdl(ll &p){
	p=0;int f(0);char z=getchar();
	while(z>'9'||z<'0'){if(z=='-')f^=1;z=getchar();}
	while(z>='0'&&z<='9')p=(p<<1)+(p<<3)+z-'0',z=getchar();
	if(f)p=-p;
}
const ll N=1e10;
ll k;
inline ll f(ll a,ll b,ll c,ll n){
	if(n<0)return 0ll;
	ll bc=b/c,n1=n+1ll,n2;
	if(n&1ll)n2=(__int128)n1/2ll*n%k;
	else n2=(__int128)n/2ll*n1%k;
	ll ans=n2*(a/c)%k+n1%k*bc%k;
	a%=c;b%=c;
	if(!a)return (n1%k*(b/c)+ans)%k;
	ll abc=floor(1.0*(a*n+b)/c);
	return (ans%k+n%k*(abc%k)%k-f(c,c-b-1ll,a,abc-1ll)+k)%k;
}
ll n,m,q;
inline ll ask1(ll z,ll w,ll kp){
	ll ans(0);
	if(w<=10000)
	for(ll j(1);j<=w;++j){
		ans+=f(m,j,kp,z-1);
	}
	else{
		for(ll i(1);i<=z;++i){
			ans+=f(1,(i-1)*m+1,kp,w-1);
		}
	}
	return ans%k;
}
ll x,y,z,w,ans;
int main(){
	rdl(n);rdl(m);rdl(q);
	while(q--){ans=0;
		rdl(x),rdl(y),rdl(z),rdl(w),rdl(k);
		for(ll p(1);p<=n*m;p*=k){
			ans+=p*((ask1(z,w,p)-ask1(z,y-1,p)-ask1(x-1,w,p)+ask1(x-1,y-1,p)+2*k)%k);
		}printf("%lld\n",ans);
	}
	return 0;
}