?

http://codeforces.com/problemset/problem/1096/E

題意：

一場游戲有p人參加，得分總和為s分，每個人的分數都是非負整數，且其中一號玩家的得分至少為r

而現在不知道具體的得分情況，求一號玩家獲勝的概率，我們認為任何一種合法的得分情況出現的概率相等

得分最高的玩家獲勝，特殊的，若有多人得分相同，他們獲勝的幾率相同

1≤p≤100，0≤r≤s≤5000，要求答案對998244353取模

---

?

這題考試的時候連暴力都沒想出來555

看題解后，感覺到了一種套路。。。

設?g(s,p,m)=（在一場總分和s，玩家數p的游戲中，沒有人得分超過m的合法狀態數）

這東西dp起來蠻簡單（的吧？），但是你會發現他的復雜度有點難以接受。。。但這至少給我們一個啟示？

• 遇到獲勝等設計隨機狀態中涉及最大值的問題，可以試著轉化成一些“不超過”問題的組合

我們試著用數學方法解決這個問題吧

?

這個?這個公式出自隔板法和容斥原理，請允許我解釋一下

首先看容斥，簡單來說就是想計算 所有情況-至少一個人超過m+至少兩個人超過m-至少三個人超過m……

然后看隔板法，如何計算有i個人超過m呢？先選出i個人C(p,i)，給每個人先分配m+1個，就變成了箱子內剩余數可以為零的經典隔板問題

這個式子在有預處理的幫助下的代價是O(p)的

有了g之后呢，答案f貌似就很好計算了，搬個公式大家自己體會吧~

總復雜度：O(s*p²)

1 #include<cstdio> 2 #define ll long long 3 #define mod 998244353 4 using namespace std; 5 ll ksm(ll x,ll t){ll ans=1;for(;t;t>>=1,x=(x*x)%mod)if(t&1)ans=(ans*x)%mod;return ans;} 6 int p,s,r; 7 ll fac[6005],invf[6005]; 8 void pre(){ 9 fac[0]=1; 10 for(int i=1;i<=p+s;i++)fac[i]=(fac[i-1]*i)%mod; 11 invf[p+s]=ksm(fac[p+s],mod-2); 12 for(int i=p+s-1;i>=0;i--)invf[i]=(invf[i+1]*(i+1))%mod; 13 } 14 ll C(ll n,ll m){ 15 if(n<0||m<0||m>n)return 0; 16 return ((fac[n]*invf[n-m])%mod*invf[m])%mod; 17 } 18 ll ans; 19 ll g(ll s,ll p,ll m){ 20 if(p==0&&s==0)return 1; 21 ll tot=0; 22 for(int i=0,t=1;i<=p;i++){ 23 tot+=t*(C(p,i)*C(s+p-1-i*(m+1),p-1)%mod); 24 tot=(tot+mod)%mod; 25 t*=-1; 26 } 27 return tot; 28 } 29 int main(){ 30 scanf("%d%d%d",&p,&s,&r); 31 pre(); 32 for(int t=r;t<=s;t++) 33 for(int q=1;q<=p;q++){ 34 ans+=((C(p-1,q-1)*ksm(q,mod-2)%mod)*g(s-q*t,p-q,t-1))%mod; 35 ans%=mod; 36 } 37 ans*=ksm(C(s+p-1-r,p-1),mod-2); 38 ans%=mod; 39 printf("%lld",ans); 40 return 0; 41 } View Code

轉載于:https://www.cnblogs.com/2017SSY/p/10207411.html

總結

以上是生活随笔為你收集整理的CF1096E The Top Scorer的全部內容，希望文章能夠幫你解決所遇到的問題。

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