Xay loves KDT.
You need to simultate the following code quickly enough.
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N=1e5+5,mo=998244353,Z=120;
inline void add(int&a,const int&b){a+=b-mo;a+=a>>31&mo;}
ull a1,a2;
ull myRand(ull &k1, ull &k2) {
ull k3 = k1, k4 = k2;
k1 = k4;
k3 ^= (k3 << 23);
k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
return k2 + k4;
}
ull rnd(){
for(;;){
ull x=myRand(a1,a2);
if(x)return x;
}
}
struct vec{
int a[Z];
inline void in(){for(int i=0;i<Z;++i)a[i]=rnd()%mo;}
};
inline int operator*(const vec&a,const vec&b){
int ans=0;
for(int i=0;i<Z;++i)ans=(ans+1ll*a.a[i]*b.a[i])%mo;
return ans;
}
struct P{
int x,y;
inline void in(){x=rnd()%mo;y=rnd()%mo;}
}a[N];
inline ll sqr(const int&x){return 1ll*x*x;}
inline ll dis(const P&a,const P&b){return sqr(a.x-b.x)+sqr(a.y-b.y);}
int n,i,j,ans;
ll R;
vec val[N];
int main(){
scanf("%d%lld%lld%lld",&n,&R,&a1,&a2);
for(i=0;i<n;++i)a[i].in(),val[i].in();
for(i=0;i<n;++i)for(j=i+1;j<n;++j)if(dis(a[i],a[j])<=R)
add(ans,val[i]*val[j]);
printf("%d\n",ans);
}
Xay still solved it easily. How about you?