自动搬运

查看原文

来自洛谷，原作者为

	lmAKf **

搬运于2025-08-24 22:22:16，当前版本为作者最后更新于2020-06-03 12:50:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

大家好，我是队爷 Imakf，这道题我考场上有细节挂了，然而这与 Imakf 强没有任何关系，请大家支持 Imakf，一起喊 Imakf 666！

然而并不是官方题解（虽然我是队爷Imakf）

---

首先很多的小朋友没有意义，把没被小朋友吃掉的概率乘起来得到每天小饼干活下来的概率 $p$。

然后 $T$ 也没有意义，我们认为是第 $T+1$ 天这个 Ysuperman 大佬会来吃东西就好啦~

然后问题变为有 $n$ 个饼干，第 $1\sim T$ 天他有 $p$ 的概率被 A 吃掉，接下来 $T+1\sim \infty$ 天每天先让 B 以 $q$ 的概率吃掉，然后 A 以 $p$ 的概率吃掉。

第一问是计算 B 期望吃多少个，我们考虑前 T 天期望剩余多少个然后计算答案即可，第 $i$ 个饼干活下来的概率是 $\frac{1}{p^T}$ 所以饼干数期望为 $n\cdot \frac{1}{p^T}$，然后每个饼干没有被 A 吃掉就被 B 吃掉，被 B 吃掉的概率是 $q\times \sum_{i=0}^{\infty} r^i$，其中 $r$ 表示活下来的概率。

第二问是计算期望多少天吃完，我们视为最晚被吃掉的饼干，那么根据 $\min-\max$ 容斥，有：

$$E(\max(S))=\sum_{T\subseteq S,T\ne \varnothing} E(\min(T))\cdot (-1)^{|T|+1} $$

注意到饼干没有区别，所以我们枚举集合大小即可：

$$E(\max(S))=\sum_{k=1}^n \binom{n}{k}(-1)^{k+1}E(\min(T)) $$

即我们需要计算集合 T 中最早被吃掉的饼干的期望时间，平凡的 trick 是认为是 $0\sim ...$ 这些时间没有被吃掉的概率和。

注意到贡献分为两端，对于 $0\sim T$ 天内，任意饼干都没有被吃的概率为 $p^{kx}$，对于第二段，活下来的概率设为 $f$，那么贡献为 $p^{Tx}\sum_{i=T+1}^{\infty} f^{(i-T)x}=p^{Tx}f^{x}\times \frac{1}{1-f^x}$，前者的贡献为 $\frac{1-p^{(T+1)x}}{1-p^x}$

加起来，直接计算即可啦~

$Code:$

如果觉得推得烦了可以看一下代码，emmm确实有点细节吧

#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int N = 2e6 + 5 ; 
const int P = 998244353 ; 
int n, m, T, p, q, fac[N], inv[N] ; 
int fpow( int x, int k ) {
	int ans = 1, base = x ; 
	while( k ) {
		if( k & 1 ) ans = ans * base % P ; 
		base = base * base % P, k >>= 1 ; 
	} return ans ;
}
int C( int x, int y ) {
	if( y > x ) return 0 ;
	return fac[x] * inv[y] % P * inv[x - y] % P ;
}
signed main()
{
	n = gi(), m = gi(), T = gi() ; 
	p = gi() ; int x ; q = 1 ; 
	rep( i, 1, m ) x = gi(), q = q * ( 1 - x + P ) % P ;
	if( ( q == 0 ) && ( T != 0 ) ) {
		puts("0 1") ; exit(0) ; 
	}
	int Tk = fpow( q, T ) * n % P ; 
	int ans1 = 0, ans2 = 0 ;
	int u = ( 1 - p + P ) * q % P ;
	if( p == 1 ) ans1 = Tk ; 
	else {
		ans1 = ( Tk * p ) % P * fpow( 1 - u + P, P - 2 ) % P ; 
	}
	inv[0] = fac[0] = 1 ; 
	rep( i, 1, n ) fac[i] = fac[i - 1] * i % P, inv[i] = fpow( fac[i], P - 2 ) ; 
	for( re int k = 1; k <= n; ++ k ) {
		int rp = C( n, k ) ; 
		if( ( k + 1 ) & 1 ) rp = ( P - rp ) % P ; 
		int tk = fpow( q, k ) ;
		int mS = fpow( tk, T ) ;
		int fk = fpow( u, k ) ; 
		int S1 = 1 ; 
		if( T ) {
			S1 = ( ( 1 - fpow( tk, T + 1 ) + P ) % P ) * fpow( 1 - tk + P, P - 2 ) % P ; 
		}
		int S2 = mS * fpow( 1 - fk + P, P - 2 ) % P * fk % P ;
		S1 = ( S1 + S2 ) % P ; 
		ans2 = ( ans2 + S1 * rp % P ) % P ;
	}
	ans1 %= P, ans2 %= P ; 
	printf("%lld %lld\n", ans1, ans2 ) ;
	return 0 ;
}