泰拳警告

• description
• solution
• code

description

題目描述
小七擅長泰拳，某天他打算與小棗切磋拳技，一共需要進(jìn)行 n 次比賽。
由于雙方拳技難分上下，每場比賽小七獲勝或落敗的概率都是 1/p+2 ，平局的概率是 p/p+2
若最后小七獲勝場數(shù)大于落敗場次，且平局次數(shù)為 k ，則能獲得 k + 1 獎勵分
小七想知道，他能獲得的獎勵分的期望是多少呢？為了避免精度誤差，你需要輸出答案在模 998244353 意義下的結(jié)果

輸入格式
輸入文件 fight.in 包含一行，輸入兩個正整數(shù)依次表示 n; p
輸出格式
輸出文件 fight.out 包含一行，僅一個非負(fù)整數(shù)，表示答案在模 998244353 意義下的結(jié)果

樣例輸入
2 1
樣例輸出
221832079

樣例解釋
兩局都勝，或勝一局平一局是合法的，期望得分為 1/3 × 1/3 ×1+2× 1/3 × 1/3 ×2 = 5/9，在模 998244353 意義下為 221832079

數(shù)據(jù)范圍及約定

測試點(diǎn)編號n特殊性質(zhì)

1 ～ 4	≤ 2000	無
5 ～ 8	≤ 105	無
9 ～ 12	≤ 3 × 106	p = 1
13 ～ 20	≤ 3 × 106	無

對于 100% 的數(shù)據(jù)，滿足 1 ≤ n ≤ 3 × 106; 1 ≤ p < 998244351 。可以證明答案一定能表示成一個既約分?jǐn)?shù) u/v，你需要找到滿足 v × w ≡ 1 mod 998244353的自然數(shù) w ，輸出 u × w mod 998244353

solution

case 0 : 上來直接搞大$DP$，$d{p}_{i,j}:$ 贏了$i$場，輸了$j$場的概率，自然就平了$n?i?j$場

枚舉每一場是贏了還是輸了甚至于平了，這是$O(n^3)$的，連最基礎(chǔ)的測試點(diǎn)都不能拿到

case 1~4 ：猜測改寫$d{p}_{i,j}:$ 在第$i$輪為止平了$j$的概率，將勝場和負(fù)場合并在一起

$d{p}_{i,j}?\frac{1}{p+2}?2\to d{p}_{i+1,j}$

$d{p}_{i,j}?\frac{p}{p+2}\to d{p}_{i+1,j+1}$

最后平了$k$場的方案數(shù)，如果勝了$i$，負(fù)了$j$；則一定對應(yīng)有一種勝了$j$，負(fù)了$i$，看似$/2$就行了，總是恰好有一種勝場大于負(fù)場

但是如果i=j，就都不能取，單獨(dú)減掉

case 5~8 : $n\le 10^5$，沒有特殊性質(zhì)，應(yīng)該是拿來給選手被卡log的安慰

case 9~12 : $p=1$，意味著勝負(fù)平都是一樣的概率，應(yīng)該可以利用數(shù)學(xué)方法計(jì)算

case 13~20 ：最后就是正解了，私以為還是p=1的數(shù)據(jù)提供了可以數(shù)學(xué)計(jì)算的靈感

枚舉平了$k$場，因?yàn)閯儇?fù)的概率一樣，所以平了$k$場的每種情況概率都是一樣的

$(\frac{p}{p+2}{)}^k?(\frac{1}{p+2}{)}^{n?k}$

每種可能其實(shí)相當(dāng)于在$n$個位置中，選$k$個為止為平，選$i$個位置為勝，剩下自然就是負(fù)

$C(n,k)?C(n?k,i)$

這里一旦枚舉$i$就又變成$n^2$了

考慮$i$的限制，勝場大于負(fù)場，即$i>n?k?i?i\in (\frac{n?k}{2},n?k]$

隨著$k$的枚舉，計(jì)算的$i$范圍也要變化，$C(n?k,i)$似乎不能通過求和然后乘以一個分?jǐn)?shù)轉(zhuǎn)移到下一個$k$，也就省不掉

考試時，在這里我陷入了僵局

思索許久無果后，我想起了與組合系數(shù)緊密相連的楊輝三角

$i$的范圍對應(yīng)在上面是一段后綴區(qū)間，斜著的不對齊，不能直觀沖擊我的數(shù)學(xué)左腦

于是乎，我果斷選擇枚舉負(fù)場次數(shù)i

這樣在楊輝三角里面就是一段左對齊的區(qū)間選址

/0123456

0	1							$2^0$
1	1	1						$2^1$
2	1	2	1					$2^2$
3	1	3	3	1				$2^3$
4	1	4	6	4	1			$2^4$
5	1	5	10	10	5	1		$2^5$
6	1	6	15	20	15	6	1	$2^6$

楊輝三角有太多的性質(zhì)了

• 第$i$行的和為$2^i$
• 每一行是對稱的

這兩個性質(zhì)便是去掉一個$n$復(fù)雜度的關(guān)鍵

因?yàn)樨?fù)場是不到一半的

e.g. 勝負(fù)場$6$，負(fù)場可能為$0/1/2$，在楊輝三角中就是減去$1+6+15$

這等于先減去中間的$C(i,\frac{i}{2})$，再除以二

e.g.勝負(fù)場$5$，負(fù)場可能為$0/1/2$，直接減去Z總和的一半

所以說負(fù)場$i$的貢獻(xiàn)可以根據(jù)$n?k$的奇偶直接算

這中間設(shè)計(jì)逆元，冪等，需要預(yù)處理后$O(1)$調(diào)用

卡的就是懶人非要在計(jì)算時反復(fù)算快速冪的$\log$

code

#include <cstdio> #define mod 998244353 #define int long long #define maxn 3000005 int n, p; int fac[maxn], inv[maxn], mi_2[maxn], Inv[maxn];int qkpow( int x, int y ) {int ans = 1;while( y ) {if( y & 1 ) ans = ans * x % mod;x = x * x % mod;y >>= 1;}return ans; }void init() {fac[0] = inv[0] = 1;for( int i = 1;i <= n;i ++ )fac[i] = fac[i - 1] * i % mod;inv[n] = qkpow( fac[n], mod - 2 );for( int i = n - 1;i;i -- )inv[i] = inv[i + 1] * ( i + 1 ) % mod;mi_2[0] = Inv[0] = 1; int mi = 1;for( int i = 1;i <= n;i ++ ) {mi_2[i] = mi_2[i - 1] * 2 % mod;mi = mi * ( p + 2 ) % mod;}Inv[n] = qkpow( mi, mod - 2 );for( int i = n - 1;i;i -- )Inv[i] = Inv[i + 1] * ( p + 2 ) % mod; }int C( int n, int m ) {return fac[n] * inv[m] % mod * inv[n - m] % mod; }signed main() {freopen( "fight.in", "r", stdin );freopen( "fight.out", "w", stdout );scanf( "%lld %lld", &n, &p );init();int ans = 0, Inv2 = qkpow( 2, mod - 2 ), mi_p = 1;for( int i = 0;i < n;i ++ ) { //平i場 int t = mi_p * Inv[i] % mod * Inv[n - i] % mod * C( n, i ) % mod;int k; //枚舉負(fù)場 if( ( n - i ) & 1 ) //勝場＋負(fù)場=奇數(shù) n-ik = mi_2[n - i - 1];elsek = ( mi_2[n - i] - C( n - i, ( n - i ) >> 1 ) + mod ) % mod * Inv2 % mod;ans = ( ans + k * t % mod * ( i + 1 ) ) % mod;mi_p = mi_p * p % mod;}printf( "%lld\n", ans );return 0; }

總結(jié)

以上是生活随笔為你收集整理的[2020-09-11 CQBZ/HSZX多校联测 T2] 泰拳警告（组合数+数学期望）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。