AGC032F - One Third 题解

题目链接：F - One Third

题目大意：洛谷

题解：这是什么神仙题目……题解不知道咋写了……大概是拿定积分推一推式子最后的出来答案是 \(\frac{1}{n}\sum_{i=1}^{n}\frac{1}{3^i\times (n-i+1)}\) ，但是我定积分都不会……

大概可以感性理解一下，枚举最小的是 k 小值，然后我们得到概率是 \(\frac{2}{3^i}\) ，然后 k 小值的期望是 \(\frac{1}{2n(n-i+1)}\cdot \frac{1}{n}\) ，然后答案就是这个东西。

代码：

#include 
int quick_power(int a,int b,int Mod){
    int ans=1;
    while(b){
        if(b&1){
            ans=1ll*ans*a%Mod;
        }
        b>>=1;
        a=1ll*a*a%Mod;
    }
    return ans;
}
const int Maxn=1000000;
const int Mod=1000000007;
const int inv_3=(Mod+1)/3;
int n;
int pow_3i[Maxn+5];
int inv[Maxn+5];
void init(){
    pow_3i[0]=1;
    for(int i=1;i<=Maxn;i++){
        pow_3i[i]=1ll*pow_3i[i-1]*inv_3%Mod;
    }
    inv[1]=1;
    for(int i=2;i<=Maxn;i++){
        inv[i]=1ll*(Mod-Mod/i)*inv[Mod%i]%Mod;
    }
}
int main(){
    init();
    scanf("%d",&n);
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=(ans+1ll*pow_3i[i]*inv[n-i+1])%Mod;
    }
    ans=1ll*ans*inv[n]%Mod;
    printf("%d\n",ans);
    return 0;
}