专栏文章

AT_utpc2020_l

xxujindong_
AT_utpc2020_l题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioi589s
此快照首次捕获于
2025/12/02 19:35
3 个月前
此快照最后确认于
2025/12/02 19:35
3 个月前
查看原文
考虑让两维变独立。我们可以对 (X−xi)2+(Y−yi)2(X-x_i)^2+(Y-y_i)^2 因式分解。通常这会用到虚数，在模意义下就是 p=299993p=299993 的二次剩余。则 (X−xi)2+(Y−yi)2=(X−xi+I(Y−yi))(X−xi−I(Y−yi))(X-x_i)^2+(Y-y_i)^2=(X-x_i+I(Y-y_i))(X-x_i-I(Y-y_i))。这就是说，将原坐标系的每个点映射至 (x+Iy,x−Iy)(x+Iy,x-Iy)，两点距离变为坐标差的乘积。
映射后，(X,Y)(X,Y) 仍然取遍 [0,p−1]×[0,p−1][0,p-1]\times[0,p-1]。对 ∏(X−xi),∏(Y−yi)\prod(X-x_i),\prod(Y-y_i) 开个桶算即可。
CPP
#include<bits/stdc++.h>
using namespace std;
const int mod=299993,I=139302;
int n,z,inv[299993],p[299993],q[299993],a[299993],b[299993];
long long ans;
int main(){
  inv[0]=inv[1]=1;
  for(int i=0;i<mod;i++)p[i]=q[i]=1;
  for(int i=2;i<mod;i++)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
  cin>>n>>z;
  for(int i=1,x,y,t;i<=n;i++){
    cin>>x>>y,t=1ll*y*I%mod,y=(x-t+mod)%mod,x=(x+t)%mod;
    for(int j=0;j<mod;j++)p[j]=1ll*p[j]*(j-x+mod)%mod,q[j]=1ll*q[j]*(j-y+mod)%mod;
  }
  for(int i=0;i<mod;i++)a[p[i]]++,b[q[i]]++;
  if(!z)return cout<<1ll*(a[0]+b[0])*mod-1ll*a[0]*b[0]<<'\n',0;
  for(int i=1;i<mod;i++)ans+=1ll*a[i]*b[1ll*z*inv[i]%mod];
  return cout<<ans<<'\n',0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...