CF1525E Assimilation IV

题目描述

  • 给定 n (1 \le n \le 20) 个城市和 m (1 \le m \le 5 \cdot 10^4) 个点.

  • 对于每个城市,给定所有点到该城市的距离与光在一秒内行走距离的比值 d (1 \le d \le n + 1)

  • 从第 0 秒开始,每隔 1 秒可以点亮 1 个未被点亮的城市.

  • 已知点亮城市的顺序随机,求第 n 秒的瞬间被照亮的点数的期望值,答案对 998244353 取模。

Solution

由于是求被照亮的点数的期望值,可以考虑单独考虑每个点被点亮的情况。

如果直接按照每个城市的顺序来考虑单个点的亮暗情况,那么就要枚举 20! 种情况,肯定是无法接受的。

那么考虑计算点被点亮的情况的补集,就是点一直不亮的情况有多少种

考虑把一个城市如果放在第 i 个位置点亮,那么他开启这个点的时间必须要严格大于 n-i+1 才可以保证在第 n 秒时,这个城市不会把这个点变亮。

C[i][j] 表示对于第 i 个点,点这个点 i 所需时间大于 j 的城市数量

那么对于点 i ,点 i 不会被点亮的情况数就是
\prod_{j=1}^n C[i][n-j+1]-(j-1)
注意此时如果有

C[i][n-j+1]-(j-1) \leq 0
那么对于点 i ,答案就是 0 。因为这说明无论城市怎样排列点 i 都一定会被点亮。

最后用总情况减去计算的答案和就是点 i 会被点亮的情况,再除以总方案就是期望。

再把所有点都考虑了,就是题目所求答案了。

#include<bits/stdc++.h>
#define ll long long
const ll mod =  998244353;
const int N = 5e4+10;
ll c[23][N];
int n,m;
ll qpow(ll a,ll b){
    if(b==0) return 1ll;
    ll c = qpow(a,b/2);
    c = c * c % mod;
    if(b&1) c = c * a % mod;
    return c;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            int x;
            scanf("%d",&x);
            c[x-1][j]++;
        }
    }
    for(int i=1;i<=m;++i)
        for(int j=n+1;j>=1;--j)
            c[j][i]+=c[j+1][i];
    ll fac = 1;
    ll ans = 0 ;
    for(int i=1;i<=n;++i) fac =1ll* fac * i % mod;
    for(int i=1;i<=m;++i){
        ll sum = 1 ;
        for(int j=1;j<=n;++j){
            if(c[n-j+1][i]-(j-1)<=0){
                sum = 0 ;
                break;
            }
            sum = sum * (c[n-j+1][i]-(j-1)) % mod;
        }
        ans = (ans + fac + mod - sum ) % mod;
    }
    ans = ans * qpow(fac,mod - 2 )%mod;
    printf("%lld\n",ans); 
    return 0;
}

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注