好吧,这是我第一次认真的搞期望有关的东西...
先说一下期望的定义吧!期望等于所有可能的情况的(权值*概率)的和...
其实在这部分我们只用注意这两个量怎么求解即可;
针对这道题,我们需要求出在牌数为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; }
做个小总结,对于这道题,因为许多的情况权值与概率都是相同的,所以我们需要讨论情况数.
对于其他的题,就......