题解：P7819 [RC-05] Xor Matrix
whileAK
·
·
题解
P7819 [RC-05] Xor Matrix
思路
$$\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)$ 算。不会类欧的可以点[这里](https://oi-wiki.org/math/number-theory/euclidean/)。这样我们只用枚举 $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;
}