7/28-7/29 期望+思维+后缀数组+ST表

期望的概念： E(X+Y)=E(X)+E(Y) 因此可根据线性的可加性做题 在条件概率中，一个事件发生的概率固定

每日一题 Game (20上海ICPC热身赛)

类型：期望题，未与dp、数学结合 思路： 1.长度为n的序列中，存在多少互质的组合cnt 2.将n分成奇偶判断，若为奇数，则会产生（n-1）/2次消去，每次概率为cnt/C(n,2); 若为偶数，则会产生n/2次消去，每次概率为cnt/C(n,2)

#include
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

using namespace std;
const int N=5e5+5;
const int mod=1e9+7;
int n;
int fac[N];
int fastpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int getinv(int a) //求逆元
{
    return fastpow(a,mod-2)%mod;
}
int C(int n,int m)  //C(n,m)
{
    return ((fac[n]*getinv(fac[m])%mod)*(getinv(fac[n-m])%mod))%mod;
}

signed main()
{
    IOS;
    cin>>n;
    int cnt=0;
    for(int i=1;i