Comet OJ - Contest #2 C 言论的阴影里妄想初萌//概率+ksm+逆元

https://cometoj.com/contest/37/problems 

题意：上面很明显了

直接枚举有1-n条边的子集的期望。

 中间卡了我好久一个问题，quick_mod(a,b,mod)，b爆int变成负数，-1>>1=-1，一直TLE。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int max_n = 1e5+6;
void exgcd(LL a, LL b, LL &x, LL &y, LL &d) {
    if (!b)
        {d = a, x = 1, y = 0;}
    else{
        exgcd(b, a % b, y, x, d);
        y -= x * (a / b);
    }
}
LL inv(LL t, LL p){
    LL d, x, y;
    exgcd(t, p, x, y, d);
    return (x % p + p) % p;
}
LL quick_mod(LL aqa,LL  nqn,LL mood){
    LL ret=1;
    while(nqn){
        if(nqn&1){
            ret=(ret*aqa)%mood;
        }
        aqa=(aqa*aqa)%mood;
        nqn=nqn>>1;
    }
    return ret;
}

int main(){
    int n,x,y;scanf("%d%d%d",&n,&x,&y);
    LL xy=x*inv(y,mod)%mod;LL ans=1+n,c=n;
    for(int i=2;i<=n;i++){
        c=c*inv(i,mod)%mod*(n-i+1)%mod;
        ans=(ans+c*quick_mod(xy,i*(i-1)/2,mod)%mod)%mod;
    }
    printf("%lld",ans);
    return 0;
}