傳送門

先看我們要求的是什么,要求的期望就是總權值/總方案,總權值可以枚舉進球的個數\(i\),然后就應該是\(\sum_{i=0}^{k} \binom{m}{i}\binom{n-m}{k-i}i^l\),總方案是\(\binom{n}{k}\)

直接做顯然不行,然后式子里有個\(i^l\),把它拆開,也就是\(\sum_{j=0}^{l} \binom{i}{j}S_{l,j}j!\),代入原式\[\sum_{i=0}^{k}\binom{m}{i}\binom{n-m}{k-i}\sum_{j=0}^{l} \binom{i}{j}S_{l,j}j!\]\[\sum_{j=0}^{l} S_{l,j}j!\sum_{i=0}^{k}\binom{m}{i}\binom{i}{j}\binom{n-m}{k-i}\]\[\sum_{j=0}^{l} S_{l,j}j!\sum_{i=0}^{k}\binom{m}{j}\binom{m-j}{i-j}\binom{n-m}{k-i}\]\[\sum_{j=0}^{l} S_{l,j}j!\binom{m}{j}\sum_{i=0}^{k}\binom{m-j}{i-j}\binom{n-m}{k-i}\]\[\sum_{j=0}^{l} S_{l,j}j!\binom{m}{j}\binom{n-j}{k-j}\]

然后只要能快速預處理出\(S_{l,j}\)就能做了.考慮組合意義\[S_{n,m}=\frac{1}{m!}\sum_{i=0}^{m}(-1)^i\binom{m}{i}(m-i)^n\]\[S_{n,m}=\sum_{i=0}^{m}\frac{(-1)^i}{i!}\frac{(m-i)^n}{(m-i)!}\]

卷積即可

這題可能有點卡常,注意簡化運算

// luogu-judger-enable-o2 #include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<vector> #include<cmath> #include<ctime> #include<queue> #include<map> #include<set> #define LL long long #define db doubleusing namespace std; const int N=2e7+10,M=550000+10,mod=998244353; LL rd() {LL x=0,w=1;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*w; } int fpow(int a,int b){int an=1;while(b){if(b&1) an=1ll*an*a%mod;a=1ll*a*a%mod,b>>=1;} return an;} int inv(int a){return fpow(a,mod-2);} int fac[N],iac[N],rdr[M]; void ntt(int *a,int n,bool op) {int x,y;for(int i=0;i<n;++i)if(i<rdr[i]) swap(a[i],a[rdr[i]]);for(int i=1;i<n;i<<=1){int ww=fpow(op?3:332748118,(mod-1)/(i<<1));for(int j=0;j<n;j+=i<<1)for(int k=0,w=1;k<i;++k,w=1ll*w*ww%mod)x=a[j+k],y=1ll*a[j+k+i]*w%mod,a[j+k]=(x+y)%mod,a[j+k+i]=(x-y+mod)%mod;}if(!op) for(int i=0,w=inv(n);i<n;++i) a[i]=1ll*a[i]*w%mod; } int C(int n,int m){return m<0||n<m?0:1ll*fac[n]*iac[m]%mod*iac[n-m]%mod;} int n,m,s,l,aa[M],bb[M],prm[M>>1],tt; bool v[M];int main() {n=rd(),m=rd(),s=rd(),l=rd();fac[0]=1;int lm=max(n,l);for(int i=1;i<=lm;++i) fac[i]=1ll*fac[i-1]*i%mod;iac[lm]=inv(fac[lm]);for(int i=lm;i;--i) iac[i-1]=1ll*iac[i]*i%mod;bb[1]=1;for(int i=2;i<=l;++i){if(!v[i]) prm[++tt]=i,bb[i]=fpow(i,l);for(int j=1;j<=tt&&i*prm[j]<=l;++j){v[i*prm[j]]=1;bb[i*prm[j]]=1ll*bb[i]*bb[prm[j]]%mod;if(i%prm[j]==0) break;}}for(int i=0;i<=l;++i)aa[i]=(i&1)?mod-iac[i]:iac[i];for(int i=0;i<=l;++i)bb[i]=1ll*bb[i]*iac[i]%mod;int len=1,ms=0;while(len<=l+l) len<<=1,++ms;for(int i=0;i<len;++i) rdr[i]=(rdr[i>>1]>>1)|((i&1)<<(ms-1));ntt(aa,len,1),ntt(bb,len,1);for(int i=0;i<len;++i) aa[i]=1ll*aa[i]*bb[i]%mod;ntt(aa,len,0);while(s--){int nn=rd(),mm=rd(),kk=rd(),ans=0,lim=min(min(l,kk),mm);for(int i=0;i<=lim;++i)ans=(ans+1ll*aa[i]/**fac[i]%mod*iac[i]%mod*/*iac[mm-i]%mod*fac[nn-i]%mod*iac[kk-i]%mod)%mod;ans=1ll*ans*inv(C(nn,kk))%mod*fac[mm]%mod*(nn>=kk?iac[nn-kk]:0)%mod;printf("%d\n",ans);}return 0; }

轉載于:https://www.cnblogs.com/smyjr/p/10992554.html

總結

以上是生活随笔為你收集整理的luogu P2791 幼儿园篮球题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。