题解：Seat [晨亦训计划-5]

DimStar
  2026-05-07 15:48:29 2026-05-07 15:48:29 创建   2026-05-07 16:12:23 2026-05-07 16:12:23 更新      1.3k 字  

Solution

首先，有个结论，就是每个小 G 选择的座位离最近小 G 的距离（简称小 G 的距离）是固定的，然后在前面的小 G 的座位固定的情况下，距离相同的小 G 们所选择的座位的可重集也是固定的。

所以就可以预处理出可能的座位，注意到此时我们没有考虑前面的小 G 选择一个偶数段的两个不同座位的情况。

形如这个东西。

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
int pos[1030], cnt[1030], even[1030]; // 分别是：第 i 行小 G 的位置，距离为 i 的座位数，选择距离为 i 的偶数长度空区间数
bool vis[1030];
void init()
{
    inv[0] = 1, inv[1] = 1;
    nmf(i, 2, n) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    vis[0] = 1, vis[n + 1] = 1;
    nmf(i, 1, n)
    {
        pair<int, int> res = {-1, -1};
        nmf(j, 0, n)
        {
            int k = j + 1;
            while (!vis[k])
                k++;
            if (k - j > res.first)
                res = {k - j, ((j + k) >> 1)};
            j = k - 1;
        }
        cnt[res.first >> 1]++;
        if (res.first & 1)
            even[res.first >> 1]++;
        pos[i] = res.second;
        vis[pos[i]] = 1;
    }
}

然后就可以按选择的距离从小到大 DP。

由于奇数长度空区间和偶数长度空区间提供的座位数不一样，为了转移就要塞进状态里。

定义 表示当前距离坐了 个小 G，还剩 个偶数长度空区间没有坐的概率。

这样的东西（len 是从小到大枚举的距离）：

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
nmf(i, 0, cnt[len]) nmf(j, 0, even[len]) f[i][j] = 0; // 初始化
f[0][even[len]] = 1;
LL fodd = 0, feven = 0; // 计算坐在 **一个** 奇数区间/偶数区间里的位置的概率
nmf(i, 0, cnt[len] - 1)
{
    fodd = 0, feven = 0;
    nmf(j, 0, even[len])
    {
        int sum = cnt[len] + j - i; // 总座位数
        if (j)
        {
            // 坐到偶数区间中间
            f[i + 1][j - 1] = (f[i + 1][j - 1] + (j * 2) * inv[sum] * f[i][j]) % mod;
            feven = (feven + (j * 2) * inv[sum] * f[i][j] * inv[even[len] * 2]) % mod;
        }
        // 坐到奇数区间中间
        f[i + 1][j] = (f[i + 1][j] + (sum - (j * 2)) * inv[sum] * f[i][j]) % mod;
        fodd = (fodd + (sum - (j * 2)) * inv[sum] * f[i][j] * inv[cnt[len] - even[len]]) % mod;
    }
    // 加到 ans 上
    nmf(l, now - cnt[len] + 1, now - cnt[len] + even[len])
        ans[now - cnt[len] + i + 1][pos[l]] += feven,
        ans[now - cnt[len] + i + 1][pos[l] + 1] += feven;
    nmf(l, now - cnt[len] + even[len] + 1, now)
        ans[now - cnt[len] + i + 1][pos[l]] += fodd;
}

因为我们没有考虑选择距离更小的小 G 的选座导致的 的可重集的不同，所以现在就要补上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define mirror(j) (j < pos[l]) ? (j + len + 1) : (j - len)
nmf(l, now - cnt[len] + 1, now - cnt[len] + even[len])
{
    int L = pos[l] - len + 1;
    int R = pos[l] + len;
    nmf(i, now + 1, n)
    {
        nmf(j, L, R)
        {
            if (j == pos[l])
                continue;
            tmp[j] = (tmp[j] + ans[i][j] * inv[2]) % mod;
            tmp[mirror(j)] = (tmp[mirror(j)] + ans[i][j] * inv[2]) % mod;
            // (j < pos[l]) ? (j + len + 1) : (j - len) 解释：
            // 若 j < pos[l]，则属于选择 pos[l] 后的 [L, pos[l] - 1] 左子区间，可以对应选择 pos[l] + 1 后的右子区间 [pos[l] + 2, R]
            // 若 j > pos[l]，则属于选择 pos[l] 后的 [pos[l] + 1, R] 右子区间，可以对应选择 pos[l] + 1 后的左子区间 [L, pos[l]]
        }
        nmf(j, L, R)
        {
            ans[i][j] = tmp[j];
            tmp[j] = 0;
        }
    }
}

很神人，初看难以理解，还得慢慢想，是道有趣的题目。

时间复杂度

。

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
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
#define nmf(i, s, e) for (int i = s; i <= e; i++)
#define ref(i, s, e) for (int i = s; i >= e; i--)
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
LL n, mod;
LL inv[1030];
LL f[1030][1030], ans[1030][1030], tmp[1030];
int pos[1030], cnt[1030], even[1030];
bool vis[1030];
void init()
{
    inv[0] = 1, inv[1] = 1;
    nmf(i, 2, n) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    vis[0] = 1, vis[n + 1] = 1;
    nmf(i, 1, n)
    {
        pair<int, int> res = {-1, -1};
        nmf(j, 0, n)
        {
            int k = j + 1;
            while (!vis[k])
                k++;
            if (k - j > res.first)
                res = {k - j, ((j + k) >> 1)};
            j = k - 1;
        }
        cnt[res.first >> 1]++;
        if (res.first & 1)
            even[res.first >> 1]++;
        pos[i] = res.second;
        vis[pos[i]] = 1;
    }
}
void solve()
{
    cin >> n >> mod;
    init();
    nmf(i, n - cnt[1] + 1, n) nmf(j, n - cnt[1] + 1, n) ans[i][pos[j]] = inv[cnt[1]];
    int now = n - cnt[1];
    nmf(len, 2, n)
    {
        if (!cnt[len])
            continue;
        nmf(i, 0, cnt[len]) nmf(j, 0, even[len]) f[i][j] = 0;
        f[0][even[len]] = 1;
        LL fodd = 0, feven = 0;
        nmf(i, 0, cnt[len] - 1)
        {
            fodd = 0, feven = 0;
            nmf(j, 0, even[len])
            {
                int sum = cnt[len] + j - i;
                if (j)
                {
                    f[i + 1][j - 1] = (f[i + 1][j - 1] + (j * 2) * inv[sum] * f[i][j]) % mod;
                    feven = (feven + (j * 2) * inv[sum] * f[i][j] * inv[even[len] * 2]) % mod;
                }
                f[i + 1][j] = (f[i + 1][j] + (sum - (j * 2)) * inv[sum] * f[i][j]) % mod;
                fodd = (fodd + (sum - (j * 2)) * inv[sum] * f[i][j] * inv[cnt[len] - even[len]]) % mod;
            }
            nmf(l, now - cnt[len] + 1, now - cnt[len] + even[len])
                ans[now - cnt[len] + i + 1][pos[l]] += feven,
                ans[now - cnt[len] + i + 1][pos[l] + 1] += feven;
            nmf(l, now - cnt[len] + even[len] + 1, now)
                ans[now - cnt[len] + i + 1][pos[l]] += fodd;
        }
#define mirror(j) (j < pos[l]) ? (j + len + 1) : (j - len)
        nmf(l, now - cnt[len] + 1, now - cnt[len] + even[len])
        {
            int L = pos[l] - len + 1;
            int R = pos[l] + len;
            nmf(i, now + 1, n)
            {
                nmf(j, L, R)
                {
                    if (j == pos[l])
                        continue;
                    tmp[j] = (tmp[j] + ans[i][j] * inv[2]) % mod;
                    tmp[mirror(j)] = (tmp[mirror(j)] + ans[i][j] * inv[2]) % mod;
                }
                nmf(j, L, R)
                {
                    ans[i][j] = tmp[j];
                    tmp[j] = 0;
                }
            }
        }
        now -= cnt[len];
    }
    nmf(i, 1, n)
    {
        nmf(j, 1, n) cout << ans[i][j] << ' ';
        cout << endl;
    }
    return;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}
  • 标题: 题解：Seat [晨亦训计划-5]
  • 作者: DimStar
  • 创建于 : 2026-05-07 15:48:29
  • 更新于 : 2026-05-07 16:12:23
  • 链接: https://dimstar-zhang.github.io/2026/05/07/题解：Seat-晨亦训计划-5/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
目录
题解：Seat [晨亦训计划-5]
  1. Solution
  2. 时间复杂度
  3. Code