2019GDCCPC省赛补题BC

    xiaoxiao2022-07-05  173

    重现赛多组输入真烦→_→,感觉如果比赛,B和E有可能题意读错会WA

     

    B Build Tree

    关键:结点总数是个等比数列和

    #include <bits/stdc++.h> using namespace std; typedef long long ll; int k; ll m,n; ll p; ll a[300000]; ll mpow(ll a, ll b) { ll ans=1; while(b) { if(b%2==1) //b&1 { ans=ans*a%p; } a=a*a%p; b/=2; //b>>=1 } return ans%p; } int main() { while(cin>>k>>m>>n>>p){ for(int i=0;i<k;i++)scanf("%lld",&a[i]); sort(a,a+k); ll sum=0; ll t=1; ll en=0; ll j=0; for(ll i=1;i<m;i++){ if(i>0)t*=n,en+=t; for(;j<en&&j<k;j++)sum=(sum+a[j]%p*((1ll-mpow(n,m-i))/(1ll-n)%p)%p)%p; //子树结点数满足等比数列 //sum=(sum+a[j]%p*((m-i)%p)%p)%p;//一个子树不只是一条路!! } cout<<sum<<endl; } }

     

    C待填

    最新回复(0)