DDOSvoid's Blog

2021杭电多校4 C Cycle Binary

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

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=6987

简要题解：给定 $n$，求所有长度为 $n$ 的 $01$ 串的价值总和，一个 $01$ 串的价值定义为 $\lfloor\frac{n}{k}\rfloor$，其中 $k$ 是这个 $01$​ 串的最小周期

$n\le 10^9$

Solution

我们令 $f(x)$ 表示最小周期为 $x$ 的长度为 $n$ 的 $01$ 串的个数，容易得到答案应该为 $\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor f(i)$

我们考虑如何求 $f(x)$，首先有一个比较容易想到的猜想，$f(x)=2^x-\sum_{y<x,y|x}f(y)$

通过周期引理，我们能够证明当 $x\le \lfloor\frac n 2\rfloor$，这个东西是正确的

而对于 $x>\lfloor\frac n 2\rfloor$ 的 $f(x)$，我们能够发现这种 $f(x)$ 的贡献的系数都是 $1$，那么我们只需要求这些 $f(x)$ 的和就行了

显然这些 $f(x)$ 的和就是 $2^n-\sum_{i=1}^{\lfloor\frac n 2\rfloor}f(i)$

那么最终的答案就是 $\sum_{i=1}^{\lfloor\frac{n}{2}}\lfloor\frac{n}{i}\rfloor f(i)+2^n-\sum_{i=1}^{\lfloor\frac n 2\rfloor}f(i)=2^n+\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}(\lfloor\frac{n}{i}\rfloor-1) f(i)$

至于 $f(x)$ 的前缀和如何求，我们发现 $2^x=\sum_{d|x}f(d)$，也就是说 $(f\circ 1)(n)=2^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
#include <iostream>
#include <vector>
#include <unordered_map>
#define ll long long
#define maxn 1000010
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; 
}

const int N = 1000000;
int f[maxn];
void init_f(int n) {
    for (int i = 1; i <= n; ++i) {
        f[i] = (f[i] + pow_mod(2, i)) % p;
        for (int j = 2 * i; j <= n; j += i) f[j] = (f[j] - f[i]) % p;
    }
    for (int i = 1; i <= n; ++i) f[i] = (f[i] + f[i - 1]) % p;
}

unordered_map<int, int> _f;
ll calc(int n) {
    if (n <= N) return f[n];
    if (_f.find(n) != _f.end()) return _f[n];
    ll ans = pow_mod(2, n + 1) - 2;
    for (int l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        ans = (ans - (r - l + 1) * calc(n / l)) % p; 
    } return _f[n] = ans;
}

int n;

void work() {
    cin >> n; ll ans = pow_mod(2, n);
    for (int l = 1, r; l <= n / 2; l = r + 1) {
        r = min(n / 2, n / (n / l));
        ans = (ans + (n / l - 1) * (calc(r) - calc(l - 1))) % p;
    } cout << (ans + p) % p << "\n";
}

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

    int T; cin >> T; init_f(N);
    while (T--) work(); 
    return 0;
}