E. Assimilation IV_牛客博客

思路：
每个点被控制之后的贡献都是 $1$ ，所以答案可以转化为求每个点被控制的期望之和。
对每个点 $u$ 计算合法排列（城市的排列），合法排列必须满足存在一个城市能控制点 $u$ ，可以用容斥/状压写，复杂度 $2^n m$ 级别的。
可以考虑求答案的补集，求每个点 $u$ 的非法排列，即所有的城市都不能控制该点，显然第 $n$ 个操作的城市于点 $u$ 的距离应该 $\geq n+1$ ，第 $n-1$ 个操作的城市于点 $u$ 的距离应该 $\geq n$ ，乘法计数原理即可。

MyCode:

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+7,mod=998244353 ;
int f[maxn][25];
int qpow(int a,int b) {
    int res(1);
    while(b) {
        if(b&1) res=1LL*res*a%mod;
        a=1LL*a*a%mod;
        b>>=1;
    }
    return res;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,m,div=1;
    cin>>n>>m;
    for(int i=1;i<=n;++i) {
        div=1LL*div*i%mod;
        for(int j=1,x;j<=m;++j){
            cin>>x;
            f[j][x]+=1;
        }
    }
    int ans(0);
    for(int i=1;i<=m;++i) {
        int tot(0),tmp(1);
        for(int j=n;j;--j) tot+=f[i][j+1],tmp=1LL*tmp*tot%mod,tot-=1;
        ans=(1LL*div-tmp+mod+ans)%mod;
    }
    cout<<1LL*ans*qpow(div,mod-2)%mod<<'\n';
    return 0;
}