题意是有 n 个城市和 m 个点，已知每个城市到每个点的距离为\(a_{ij}\)，每秒进行一次操作，每次随机选一个没选过的城市建一个碑，其影响的范围每秒加一，求 n 秒后被影响的点数的期望。
朴素的想法是\(n!\)枚举建碑的方案，然后暴力判断每种方案能覆盖多少点，但n最大为20，枚举阶乘显然会t。这时就要用到概率题目的常见思想：转变所求目标。既然方案不好考虑，那么就考虑点。我们要求的期望实际上是\(E(\Sigma_{i=1}^mI(i))\)，其中\(I(x)\)是指示函数，由期望的线性性质，\(E(\Sigma_{i=1}^mI(i))=\Sigma_{i=1}^mE(I(i))=\Sigma_{i=1}^mp(i)\)，\(p(i)\)即这个点被覆盖的概率。因为每种建碑方案会将点与点之间联系起来，因此使用线性性质可以将问题转化为单独求每个点的概率。因为每个点可能会被重复覆盖，所以将每个点被覆盖的概率转化为1-不被覆盖的概率。设当前考虑的点为i，将n个碑到i的距离从小到大排序。设最近的那个碑到当前点的距离为d[0]，那么需要把它放到后d[0]-1个位置中的某个位置（这样才能保证这个碑永远不会覆盖到当前点）；次近的碑需要放到后d[1]-1-1个位置（为什么d[1]-1以后还要再减1？因为按照距离排序后，前一个碑肯定已经在后d[1]-1个位置中占据一个了）…由乘法原理，可得当前点不被覆盖的概率为\(\frac{1}{n!}\Pi_{i=0}^{n-1}max(0, d[i]-1-i)\)，和0取max是因为如果减为负数说明当前点无论如何都会被覆盖。\(1-\frac{1}{n!}\Pi_{i=0}^{n-1}max(0, d[i]-1-i)\)就是当前点被覆盖的概率。对所有的点求概率，相加即为答案。
#include <bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int n, m;
int d[25][50005];
int fpow(int a, int b) {
int ans = 1;
for(; b; b >>= 1) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
}
return ans;
}
void solve() {
cin >> n >> m;
int inv = 1;
for(int i = 1; i <= n; i++) {
inv = inv * fpow(i, mod - 2) % mod;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> d[i][j];
}
}
int ans = 0;
for(int i = 1; i <= m; i++) {
vector<int> v;
for(int j = 1; j <= n; j++) {
v.push_back(d[j][i]);
}
sort(v.begin(), v.end());
int tmp = 1;
for(int j = 0; j < v.size(); j++) {
tmp = tmp * max(0ll, v[j] - 1 - j) % mod;
}
tmp = tmp * inv % mod;
tmp = (1 - tmp + mod) % mod;
ans = (ans + tmp) % mod;
}
cout << ans << endl;
}
signed main() {
int T = 1;
while(T--) {
solve();
}
}
原文地址：http://www.cnblogs.com/lipoicyclic/p/16882196.html
