CF1525E

Erica_N_Contina · 2023-10-20 21:12:48 · 题解

大意

给出光从每一座城市到每一个点的用时，从第零秒开始，每隔一秒可以点亮一个未被点亮的城市，城市发出的光可以点亮点，求第 n 秒的瞬间被点亮的点数的期望值。

思路

是一道不擅长的期望题！

首先我们对于每个点单独计算它被选中的概率，再求和即为答案。

我们发现一种情况和一个长度为 n 的排列（即点亮城市的顺序)一一对应，所以考虑当前点在多少个排列中被覆盖。

如果有某座城市的光覆盖当前点，那么一定存在排列的第 i 位是距离 ≤i 的城市。那么 i 可能有很多个，我们要计算这种情况的情况数，我们很容易想到排列组合里的一个技巧——计算不成立的情况。

正难则反。直接计算不好求，那我们就考虑计算没有覆盖当前点。

如果没有覆盖当前点，那么排列的最后一位一定是距离 >n 的城市，倒数第二位一定是距离 >n-1 的城市，依次类推，我们直接乘法原理计算即可。注意，因为我们每座城市都会被点亮，所以如果有一个城市距离当前点的距离为 1，那么这个点一定会被点亮。

按照这种方法暴力，我们的复杂度为 O(m\times n^2) 大概是 2\times 10^7，经过优化和桶计数，我们可以优化为 O(nm)。

代码

/*////////ACACACACACACAC///////////
       . Code  by  Ntsc .
       . Earn knowledge .
/*////////ACACACACACACAC///////////

#include<bits/stdc++.h>
#define int long long
#define db double
#define rtn return
using namespace std;

const int N=1e5+5;
const int M=1e5;
const int MOD=998244353;
const int INF=1e5;

int n,m,p,q,T,fac[N],ans;
int c[N][22];

int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return res;
}

int rd(){
    int t;
    cin>>t;
    return t;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        c[j][rd()]++;//c[j][k]表示离点j距离为k的点的个数
    }
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=(i*fac[i-1])%MOD;
    int inv=ksm(fac[n],MOD-2);
    for(int i=1;i<=m;i++){
        int sum=0,tmp=1;
        for(int j=n;j;j--){
            sum+=c[i][j+1];
            tmp=tmp*sum%MOD;
            sum--;
        }
        ans=(ans+1-inv*tmp%MOD+MOD)%MOD;//1为总方案的概率，inv*tmp为不合法的概率
    }
    cout<<ans<<endl;               
}