题解 P6595 【[YsOI2020]计划】

· · 题解

大家好，我是队爷 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 ;
}