Circular Mirror

发表于 更新于 分类于 ，

    在一个圆上有n个点，现在给出相邻两个点之间的弧长。

    然后你需要将n个点涂色，你有m种颜色可以涂。要保证形成的直角三角形的三个点不能是同一种颜色。

    然后求涂色的可行方案数，模998244353

Circular Mirror

Created by LXC on Mon May 15 00:17:58 2023

https://codeforces.com/problemset/problem/1725/C

ranting: 2000

tag: binary search, combinatorics, geometry, math, two pointers

题意

在一个圆上有n个点，现在给出相邻两个点之间的弧长。

然后你需要将n个点涂色，你有m种颜色可以涂。要保证形成的直角三角形的三个点不能是同一种颜色。

然后求涂色的可行方案数，模998244353

题解

根据圆周角定理，圆上的三个点形成了直角三角形，那么肯定有两个点可以成为圆的直径。

如果直径上的点是同一种颜色，那么这种颜色就不能再用了。

我们先统计有多少条直径，假设有k条，那么就有n-2k个非直径上的点。

设当直径上的两个点颜色相同的直径条数为x条时，涂色方案数为$f_x$。

我们可以从k条中无顺序选出x条，共计$C_k^x$。

然后对这x条直径可以从m种颜色种有顺序选取x种，共计$A_m^x$

最后剩余m-x种颜色，剩余k-x条直径，对于剩余的直径，两个点颜色必须不相同，所以每条直径可以选的颜色有$C_{m-x}^2=(m-x)*(m-x-1)$，那么对于k-x条直径共计$(C_{m-x}^2)^{k-x}$

最后对于非直径上的点能用的颜色也是m-x种，所以共计$(m-x)^{n-2k}$

根据乘法原理，$f_x = C_{k}^{x}A_{m}^{x}(C_{m-x}^{2})^{k-x}(m-x)^{n-2k}$

根据加法原理，所有涂色方案数为$\sum \limits_{x=0}^{min(k,m)}f_x$

可以先预处理所有阶乘和阶乘逆元，计算组合数。
以及使用快速幂计算幂次。

代码

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

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

ll fpow(ll x, ll p) {
    ll rt = 1;
    while (p) {
        if (p & 1)
            rt = rt * x % MOD;
        x = x * x % MOD;
        p >>= 1;
    }
    return rt;
}

ll fac[N], inv[N];

ll a[N];

void sol() {
    ll n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    if (a[n] % 2) {
        cout << fpow(m, n) << "\n";
        return;
    }

    fac[0] = 1;
    for (int i = 1; i < N; i++) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    inv[N - 1] = fpow(fac[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; i--) {
        inv[i] = inv[i + 1] * (i + 1) % MOD;
    }

    ll k = 0;
    map<ll, int> mp;
    mp[0] = 0;
    for (int i = 1; i < n; i++) {
        if (mp.count(a[i] - a[n] / 2)) {
            k++;
        }
        mp[a[i]] = i;
    }

    ll ans = 0;
    for (ll x = 0; x <= min(m, k); x++) {
        ll r = 1;
        r = r * fac[k] % MOD;
        r = r * inv[k - x] % MOD;
        r = r * inv[x] % MOD;
        r = r * fac[m] % MOD;
        r = r * inv[m - x] % MOD;
        r = r * fpow((m - x) * (m - x - 1) % MOD, k - x) % MOD;
        r = r * fpow(m - x, n - 2 * k) % MOD;
        ans += r;
        ans %= MOD;
    }
    cout << ans << "\n";
}

int main() {
    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;
}