xay loves KDT
题号:NC225174
时间限制:C/C++/Rust/Pascal 8秒,其他语言16秒
空间限制:C/C++/Rust/Pascal 1024 M,其他语言2048 M
64bit IO Format: %lld

题目描述

Xay loves KDT.
One day, Xay meet a problem called the closest pair of points on plane set. Then he solved it easily with KDT.
Today, Xay meet another problem. 
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?

输入描述:

The first line contains four integers n,R,a1,a2  indicating the input of the code which you need to simulate.

输出描述:

Print a single integer, represents the output of the code which you need to simulate.
示例1

输入

复制
100 267803336482924225 400265358317882021 235154234845542156

输出

复制
694203853

备注:

Please check the time complexity of the code submitted by you.