被这题恶心死了
对于矩阵比较小的可以暴力做。
容易发现这个 \(k\) 进制下异或和是可以容斥的。
枚举答案的位数 \(p\)，即求：
\[\sum_{i=1}^{x}\sum_{j=1}^{y}\lfloor\frac{(i-1)m+y}{k^p}\rfloor\mod k
\]
然后利用类欧可以得到两种做法：
- 枚举 \(i\)，求
\[\sum_{i=1}^{x}f(1,(i-1)m,k^p,y)-\lfloor\frac{(i-1)m}{k^p}\rfloor
\]
- 枚举 \(j\)，求
\[\sum_{j=1}^{y}f(m,j,k^p,x-1)
\]
第一个式子的 \(a=1\)，所以复杂度可以看作是 \(\text{O}(n)\) 的，但是第二个式子有可能会变成 \(\text{O}(m\log V)\) .
平衡一下，当 \(n=\frac{V}{n}\log V\) 时最劣，取 \(n=(V\log V)^{\frac{1}{2}}\)，复杂度 \(\text{O}(q\log_k V\cdot(V\space\text{log}\space V)^{\frac{1}{2}})\)，可以通过。
细节很多，注意 long long 溢出，使用取模优化。
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define L 35
#define V 1500000
using namespace std;
il ll read(){
ll x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
ll n,m,q;
ll x,y,_x,_y,k;
il ll mul(ll a,ll b){
ll r=((long double)a/k*b+0.5);
r=a*b-r*k;
return r<0?r+k:r;
}
il ll val(ll n){
ll ret1=n,ret2=n+1;
n&1?ret2>>=1:ret1>>=1;
return mul(ret1,ret2);
}
il ll md(ll a){
return a<k?a:a%k;
}
il ll add(ll a,ll b){
a+=b;
return a>k?a-k:a;
}
il ll mns(ll a,ll b){
return a<b?a-b+k:a-b;
}
il ll f(ll a,ll b,ll c,ll n){
ll A=a/c,B=b/c;
if(!a)return md((n+1)*B);
if(A||B){
ll ret=0;
if(A)ret=md(val(n)*A);
ret=add(ret,md((n+1)*B));
return add(ret,f(a%c,b%c,c,n));
}
ll M=(a*n+b)/c;
return mns(mul(n,M),f(c,c-b-1,a,M-1));
}
ll sum[L];
il ll calc(ll x,ll y,ll cur){
if(!x||!y)return 0;
ll ret=0;
if(x<=y*L){
for(ll i=1;i<=x;i++)
ret=add(ret,mns(f(1,(i-1)*m,cur,y),md((i-1)*m/cur)));
}
else{
for(ll j=1;j<=y;j++)
ret=add(ret,f(m,j,cur,x-1));
}
return ret;
}
int main(){
n=read(),m=read(),q=read();
while(q--){
memset(sum,0,sizeof(sum));
x=read(),y=read(),_x=read(),_y=read(),k=read();
if((_x-x+1)*(_y-y+1)<=V){
for(ll i=x;i<=_x;i++)
for(ll j=y;j<=_y;j++){
ll cur=(i-1)*m+j,cnt=0;
while(cur){
(sum[cnt++]+=cur%k)%=k;
cur/=k;
}
}
}
else{
for(ll i=0,cur=1;i<L;i++){
sum[i]=calc(_x,_y,cur)-calc(_x,y-1,cur)-calc(x-1,_y,cur)+calc(x-1,y-1,cur);
sum[i]=(sum[i]%k+k)%k;
if(n*m/k<cur)break;cur*=k;
}
}
ll ans=0;
for(ll i=0,cur=1;i<L;i++){
ans+=sum[i]*cur;
if(n*m/k<cur)break;cur*=k;
}
printf("%lld\n",ans);
}
return 0;
}