好吧,这是我第一次认真的搞期望有关的东西...

先说一下期望的定义吧!期望等于所有可能的情况的(权值*概率)的和...

其实在这部分我们只用注意这两个量怎么求解即可;

针对这道题,我们需要求出在牌数为i时的情况数,因为权值与概率都很显然...

显然有两个状态,有相同的牌,与没有相同的牌,所以我们需要用递推求解,对于计数类问题大部分是排列与组合的关系...

之后就没了,这里需要尽可能的优化,记住(若q为a的逆元,则q2也是a2的逆元)...

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=10000100,mod=998244353;
ll Q,f[N][2],n,ans,ss,s1;//f[i][0]表示到到第i个数时没选到的情况数,1表示选到... 
inline int read()
{
    int x=0,ff=1;
    char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*ff;
}
inline ll kuaisu(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y&1) ans=(ans*x)%mod;
        y>>=1;
        x=(x*x)%mod;
    }
    return ans;
}
inline void put(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) put(x/10);
    putchar(x%10+'0');
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    Q=read();
    while(Q--)
    {
        n=read();
        if(n==1) {printf("2\n");continue;}
        f[1][0]=n;ans=0;s1=kuaisu(n,mod-2);ss=s1;
        for(register int i=2;i<=n+1;++i)
        {
            f[i][0]=(f[i-1][0]*(n-i+1))%mod;
            f[i][1]=(f[i-1][0]*(i-1))%mod;ss=(ss*s1)%mod;
            ans=(ans+((f[i][1]*i)%mod*ss))%mod;
        }
        put(ans);puts("");
    }
    return 0;
}

做个小总结,对于这道题,因为许多的情况权值与概率都是相同的,所以我们需要讨论情况数.

对于其他的题,就......

02-12 01:27