DDOSvoid's Blog

2021杭电多校1 K Necklace of Beads

发表于 更新于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

题目描述

http://acm.hdu.edu.cn/showproblem.php?pid=6960

简要题意：求有多少个长度为 $n$ 的循环同构的序列，每个位置最多只有三种颜色，红绿蓝，要求绿色不能出现超过 $k$ 次，且相邻的位置颜色不能相同

$n,k\le 10^6$

Solution

首先我们知道答案就是这个式子 $\frac 1 n \sum_{i=1}^n\sum_{j=0}^{\lfloor \frac{m(i,n)}{n}\rfloor}f((i,n),j)$ 其中 $f(n,m)$ 表示大小为 $n$ 的环染色，其中绿色的个数为 $m$

首先我们考虑如何计算 $f(n,m)$

首先我们考虑绿色不放在 $1$ 或 $n$ 的位置，那么两个绿色之间有且仅有两种填法，那么答案就是 $2^m\binom{n-m}{m}$

然后我们考虑将绿色放在 $1$ 或 $n$ 的位置，容易知道这两种情况的方案数相同，下面仅考虑放在 $1$ 的情况，容易得到答案是 $2^{m-1}\binom{n-m-1}{m-1}$，注意这个东西还要乘个 $2$

那么 $f(n,m)=2^m(\binom{n-m}{m}+\binom{n-m-1}{m-1})$

我们考虑化简总的答案，容易得到 $\frac 1 n \sum_{d|n} \varphi(\frac n d)\sum_{i=0}^{\lfloor \frac{m(i,n)}{n}\rfloor}f(d, i)$

我们直接枚举约数然后 $O(n)$ 计算即可

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
#include <iostream>
#include <vector>
#define maxn 1000010
#define ll long long
#define INF 1000000000
using namespace std;

const int p = 998244353;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s;
}

ll pow2[maxn];
void init_pow2(int n) { pow2[0] = 1; for (int i = 1; i <= n; ++i) pow2[i] = pow2[i - 1] * 2 % p; } 

ll fac[maxn], inv[maxn];
void init_C(int n) {
    fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % p;
    inv[n] = pow_mod(fac[n], p - 2);
    for (int i = n - 1; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % p; 
}

ll C(int n, int m) { return n < m ? 0 : fac[n] * inv[m] % p * inv[n - m] % p; }

int pri[maxn], cnt, phi[maxn]; bool isp[maxn];
void init_isp(int n) {
    phi[1] = 1; 
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i, phi[i] = i - 1; 
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) { phi[i * pri[j]] = phi[i] * pri[j]; break; }
            phi[i * pri[j]] = phi[i] * (pri[j] - 1); 
        }
    }
}

int n, m;

ll ans; 
void solve(int d) {
    ll sum = (d & 1) ? 0 : 2; 
    for (int i = 1; i <= 1ll * m * d / n; ++i)
        sum = (sum + pow2[i] * (C(d - i, i) + C(d - i - 1, i - 1))) % p;
    ans = (ans + sum * phi[n / d]) % p; 
}

void work() {
    cin >> n >> m; ans = 0; 
    for (int p = 1; p * p <= n; ++p) {
        if (n % p == 0) solve(p);
        if (n % p == 0 && n / p != p) solve(n / p); 
    } cout << ans * pow_mod(n, p - 2) % p << "\n"; 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    init_pow2(1000000); init_isp(1000000); init_C(1000000);
    
    int T; cin >> T;
    while (T--) work(); 
    return 0;
}