Assimilation IV

发表于 分类于 ，

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

    • 对于每个城市，给定所有点到该城市的距离与光在一秒内行走距离的比值 $d$ ($1 \le d \le n + 1$)（不一定满足三角不等式）.

    • 从第零秒开始，每隔一秒可以点亮一个未被点亮的城市.

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

Assimilation IV

Created by LXC on Wed Feb 14 14:49:20 2024

https://codeforces.com/problemset/problem/1525/E

ranting: 2100

tag: combinatorics, dp, math, probabilities, two pointers

problem

  • 给定 $n$ ($1 \le n \le 20$) 个城市和 $m$ ($1 \le m \le 5 \cdot 10^4$)个点.
  • 对于每个城市，给定所有点到该城市的距离与光在一秒内行走距离的比值 $d$ ($1 \le d \le n + 1$)（不一定满足三角不等式）.
  • 从第零秒开始，每隔一秒可以点亮一个未被点亮的城市.
  • 已知点亮城市的顺序随机，求第 n 秒的瞬间被照亮的点数的期望值,答案对 998244353 取模。

solution

期望=所有方案的结果值之和/方案总数

总方案数为$n!$种，每一种方案的结果值是计算“点亮城市的排列”对应的照亮点的个数。

我们可以考虑每个点对总结果值之和的贡献。

现在考虑第i个点的贡献，对应某种方案，至少有一个城市能覆盖第i个点那么这种方案中第i个点的贡献就是1。至少有一个城市能覆盖第i个点=总方案数-一个都没有覆盖第i个点。

考虑构造一个城市都没有覆盖第i个点的排列。排列在第一个点亮的城市其距离必须大于n，第二个点亮的城市其距离必须大于n-1。。。

设$d_i$是第i个点到各个城市中距离大于i的城市数量
覆盖第i个点的排列数就有$d_n \times (d_{n-1} - 1) \times (d_{n-2} - 2) \times \cdots \times (d_{1} - n + 1)$个。这也是第i个点的贡献。

$d_{n-1}$个距离大于i的城市，在此之前已经选过一个城市了，所以只有$$d_{n-1}-1$中选择。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

#define N 100005
ll fac[N], inv_fac[N];

ll fpow(ll x, ll p, ll m) {
	ll rt = 1;
	while (p) {
		if (p&1) rt *= x, rt %= m;
		x *= x; x %= m;
		p >>= 1;
	}
	return rt;
}
void pre() {
    fac[0] = 1;
    for (int i=1; i<N; i++) {
        fac[i] = fac[i-1]*i%MOD;
    }
    inv_fac[N-1] = fpow(fac[N-1], MOD-2, MOD);
    for (int i=N-2; i>=0; i--) {
        inv_fac[i] = inv_fac[i+1]*(i+1)%MOD;
    }
}
int comb(int n, int m) {
	return fac[n]*inv_fac[m]%MOD*inv_fac[n-m]%MOD;
}

void sol() {
    pre();
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n, vector<int>(m));
    for (auto& i:g) {
        for (auto& j:i) {
            cin >> j;
        }
    }
    ll ans = 0;
    for (int i=0; i<m; i++) {
        vector<int> d(n+2);
        for (int j=0; j<n; j++) {
            d[g[j][i]-1]++;
        }
        // cout << d << endl;
        for (int j=n; j>=0; j--) {
            d[j] += d[j+1];
        }
        // cout << d << endl;
        ll sub = 1;
        for (int j=n; j>0; j--) {
            sub *= d[j]-n+j;
            sub %= MOD;
        }
        ans += ((fac[n]-sub)%MOD+MOD)%MOD;
        ans %= MOD;
    }
    cout << ans*inv_fac[n]%MOD << endl;
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}