Advertisement
yicongli

T147T2

Mar 10th, 2019
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.16 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8. #define ull unsigned long long
  9.  
  10. template<typename T>
  11. inline void read(T&x){
  12.     x=0;T k=1;char gc;
  13.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  14.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  15. }
  16.  
  17. const int N=1e5+7;
  18.  
  19. int n;
  20. ll p,A,B;
  21.  
  22. inline ll add(ll a,ll b){
  23.     return (a+=b)>=p?a-p:a;
  24. }
  25.  
  26. inline ll sub(ll a,ll b){
  27.     return (a-=b)<0?a+p:a;
  28. }
  29.  
  30. inline ll mul(ll a,ll b){
  31.     ll ans=0;
  32.     if(a<b)swap(a,b);
  33.     while(b){
  34.         if(b&1)ans=add(ans,a);
  35.         a=add(a,a);
  36.         b>>=1;
  37.     }
  38.     return ans;
  39. }
  40.  
  41. inline ll qpow(ll a,ll b){
  42.     ll ans=1;
  43.     while(b){
  44.         if(b&1)ans=mul(ans,a);
  45.         a=mul(a,a);
  46.         b>>=1;
  47.     }
  48.     return ans;
  49. }
  50.  
  51. ll w;
  52.  
  53. struct comp{
  54.     ll x,y;
  55.     inline comp(ll a,ll b):x(a),y(b){}
  56. };
  57.  
  58. inline comp operator + (const comp &a,const comp &b){
  59.     return comp(add(a.x,b.x),add(a.y,b.y));
  60. }
  61.  
  62. inline comp operator * (const comp &a,const comp &b){
  63.     return comp(add(mul(a.x,b.x),mul(w,mul(a.y,b.y))),add(mul(a.x,b.y),mul(a.y,b.x)));
  64. }
  65.  
  66. inline comp qpow(comp a,ll b){
  67.     comp ans(1,0);
  68.     while(b){
  69.         if(b&1)ans=ans*a;
  70.         a=a*a;
  71.         b>>=1;
  72.     }
  73.     return ans;
  74. }
  75.  
  76. inline ull rnd0(){
  77.     return rand();
  78. }
  79.  
  80. inline ull rnd1(){
  81.     return (rnd0()<<16)|rnd0();
  82. }
  83.  
  84. inline ull rnd2(){
  85.     return (rnd1()<<32)|rnd0();
  86. }
  87.  
  88. inline ull rnd(ll l,ll r){
  89.     return l+rnd2()%(r-l+1);
  90. }
  91.  
  92. inline ll check(ll x){
  93.     return qpow(x,(p-1)/2);
  94. }
  95.  
  96. inline ll Sqrt(ll x){
  97.     if(x==0)return 0;
  98.     if(check(x)==p-1)return -1;
  99.     ll t=rnd(1,p-1);
  100.     while(1){
  101.         w=sub(mul(t,t),x);
  102.         if(check(w)==p-1)return qpow(comp(t,1),(p+1)/2).x;
  103.         t=rnd(1,p-1);
  104.     }
  105. }
  106.  
  107. int fa[N];
  108. ll a[N];
  109. vector<int>G[N];
  110.  
  111. ll ans,rt,t1,t2;
  112. map<ll,int>cnt;
  113.  
  114. void dfs(int x){
  115.     if(a[x]==0)ans+=cnt[0];
  116.     else if(~rt){
  117.         ans+=cnt[mul(a[x],t1)];
  118.         if(t2!=t1)ans+=cnt[mul(a[x],t2)];
  119.     }
  120.     cnt[a[x]]++;
  121.     for(int i=0;i<G[x].size();++i){
  122.         dfs(G[x][i]);
  123.     }
  124.     cnt[a[x]]--;
  125. }  
  126.  
  127. int main(){
  128.     freopen("mikan.in","r",stdin);
  129.     freopen("mikan.out","w",stdout);
  130.     r(n),r(p),r(A),r(B);
  131.     for(int i=1;i<=n;++i)r(a[i]);
  132.     for(int i=2;i<=n;++i){
  133.         r(fa[i]);
  134.         G[fa[i]].push_back(i);
  135.     }
  136.     rt=Sqrt(sub(mul(A,A),4*B%p));
  137.     (B*=2)%=p;
  138.     B=qpow(B,p-2);
  139.     t1=mul((p-A+rt)%p,B);
  140.     t2=mul((2*p-A-rt)%p,B);
  141.     dfs(1);
  142.     printf("%lld\n",ans);
  143. }
  144. /*
  145. 5 7 5 6
  146. 4 6 2 2 3
  147. 1 1 2 2
  148.  
  149. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement