Martian148's blog Martian148's blog
首页
  • ICPC 算法笔记
  • ICPC 算法题解
  • 体系结构
  • 高等数学
  • 线性代数
  • 概率论与数理统计
  • 具体数学
  • Martian148的奇思妙想
  • 游记
  • 通识课笔记
关于
  • useful 网站
  • 友情链接
  • 分类
  • 归档

Martian148

一只热爱文科的理科生
首页
  • ICPC 算法笔记
  • ICPC 算法题解
  • 体系结构
  • 高等数学
  • 线性代数
  • 概率论与数理统计
  • 具体数学
  • Martian148的奇思妙想
  • 游记
  • 通识课笔记
关于
  • useful 网站
  • 友情链接
  • 分类
  • 归档
  • codeforses 题解

  • atcoder 题解

    • AtCoder Beginner Contest 344 A-G 题解
    • AtCoder Beginner Contest 345 A-F 题解
      • A - Leftrightarrow
        • Question
        • Solution
        • Code
      • B - Integer Division Returns
        • Quesiton
        • Solution
        • Code
      • C - One Time Swap
        • Question
        • Solution
        • Code
      • D - Tiling
        • Quesiton
        • Solution
        • Code
      • E - Colorful Subsequence
        • Question
        • Solution
        • Code
      • F - Many Lamps
        • Question
        • Solution
        • Code
      • G - Sugoroku 5
        • Question
        • Solution
        • Code
    • AtCoder Beginner Contest 346 A-G 题解
    • AtCoder Beginner Contest 347 A-G 题解
    • AtCoder Beginner Contest 353 A-G 题解
    • AtCoder Beginner Contest 359 A-G 题解
    • AtCoder Beginner Contest 366 A-F 题解
    • AtCoder Beginner Contest 369 A-F 题解
  • XCPC 题解

  • 校训练赛题解

  • 牛客题解

  • 蓝桥杯题解

  • 典题选讲

  • 杂题

  • 算法题解
  • atcoder 题解
martian148
2024-08-02
目录

AtCoder Beginner Contest 345 A-F 题解

AtCoder Beginner Contest 345 (opens new window)

# A - Leftrightarrow

# Question

给你一个由 <、= 和 > 组成的字符串 SSS 。

请判断 SSS 是否是双向箭头字符串。

字符串 SSS 是双向箭头字符串,当且仅当存在一个正整数 kkk ,使得 SSS 是一个 <、 kkk 个 = 和一个 >的连接,且顺序如此,长度为 (k+2)(k+2)(k+2) 。

# Solution

按照题意模拟

# Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    if (s[0] != '<') {printf("No\n"); return 0;}
    if (s.back() != '>') {printf("No\n"); return 0;}
    for (int i = 1; i < s.size() - 1; i++) {
        if (s[i] != '=') {printf("No\n"); return 0;}
    }
    printf("Yes\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

# B - Integer Division Returns

# Quesiton

给定一个介于 −1018-10^{18}−1018 和 101810^{18}1018 之间的整数 XXX ,打印 ⌈X10⌉\left\lceil \dfrac{X}{10} \right\rceil⌈10X​⌉ 。
这里, ⌈a⌉\left\lceil a \right\rceil⌈a⌉ 表示不小于 aaa 的最小整数。

# Solution

分类讨论,如果 aaa 能整除 101010,那么答案就是 a10\frac{a}{10}10a​

  • 如果 aaa 是正数,输出 ⌊a10⌋+1\lfloor \frac{a}{10}\rfloor + 1⌊10a​⌋+1

  • 如果 aaa 是负数,输出 ⌊a10⌋\lfloor \frac{a}{10}\rfloor⌊10a​⌋

# Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll n; cin >> n;
    if (n % 10 == 0) {
        cout << n / 10 << '\n';
    }
    else {
        if (n > 0) {
            cout << n / 10 + 1 << '\n';
        }
        else {
            cout << n / 10 << '\n';
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# C - One Time Swap

# Question

给你一个字符串 SSS 。请找出以下操作 111 次的字符串数。

  • 设 NNN 是 SSS 的长度。选择一对整数 (i,j)(i,j)(i,j) 使得 1≤i<j≤N1\leq i\lt j\leq N1≤i<j≤N 和 SSS 的 iii -th 和 jjj -th 字符互换。

# Solution

考虑交换的对数是 n(n+1)2\frac{n(n+1)}{2}2n(n+1)​

如果一个字母,和之前相同的字母交换,得到的还是原串,否则得到的串是一个新串

所以我们只需要统计每个字符与之前的多少个字母不同就可以得到答案

注意要判断是否能得到原串

# Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    string s; cin >> s;
    ll n = s.size(); s = " " + s;
    vector<ll> num(26,0);
    ll ans = 0, flg = 0;
    for (int i = 1; i <= n; i++) {
        if (num[s[i] - 'a'] > 0) flg = 1;
        num[s[i] - 'a']++;
        ans += i - num[s[i] - 'a'];
    }
    cout << ans + flg << '\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# D - Tiling

# Quesiton

有一个由 HHH 行和 WWW 列组成的网格,每个单元格的边长为 111 ,我们有 NNN 块瓷砖。
其中的 iii 瓷砖( 1≤i≤N1\leq i\leq N1≤i≤N )是一个大小为 Ai×BiA_i\times B_iAi​×Bi​ 的矩形。
请判断是否有可能将这些瓷砖放置在网格上,从而满足以下所有条件:

  • 每个单元格都正好被一个图块覆盖。
  • 有未使用的瓦片也没关系。
  • 瓷砖在放置时可以旋转或翻转。但是,每块瓦片必须与单元格的边缘对齐,不得超出网格。

N≤7,H,W≤10N\le7,H,W\le 10N≤7,H,W≤10

# Solution

考虑到 N,H,WN,H,WN,H,W 都特别小,直接暴力

直接枚举放瓷砖的顺序以及每块砖是否旋转,最后暴力放砖即可

我在放砖的时候使用了优先队列,所以时间复杂度为 O(HWlog⁡HW)O(HW\log HW)O(HWlogHW)

实际上判断放砖可以优化到 O(HW)O(HW)O(HW)

总时间复杂度就为 O(N!⋅2N⋅HW)O(N!\cdot 2^N\cdot HW)O(N!⋅2N⋅HW)

# Code

#include <bits/stdc++.h>
using namespace std;

typedef vector<vector<int> > vvi;
typedef pair<int, int> pii;


int main() {
    int n; cin >> n;
    int H, W; cin >> H >> W;
    vector<pii> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
    }

    auto check = [&]  (vector<int> &id, int S) {
        vector<vector<int> > v(H + 1, vector<int>(W + 1,0));
        priority_queue<pii, vector<pii>, greater<pii> > pq;
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                pq.push({i,j});
            }
        }
        for (int i = 1; i <= n; i++) {
            auto &[dx, dy] = a[id[i]];
            if (S >> (i - 1) & 1) 
                swap(dx, dy);
            while (!pq.empty() && v[pq.top().first][pq.top().second]) pq.pop();
            if (pq.empty()) {return 1;}
            auto [x, y] = pq.top(); pq.pop();
            for (int i_ = x; i_ < x + dx; i_++) {
                for (int j_ = y; j_ < y + dy; j_++) {
                    if (i_ > H || j_ > W || v[i_][j_] == 1) return 0;
                    v[i_][j_] = 1;
                }
            }
        }
        while (!pq.empty() && v[pq.top().first][pq.top().second]) pq.pop();
        if (pq.empty()) return 1;
        return 0;
    };

    vector<int> id (n + 1);
    iota(id.begin(), id.end(), 0);
    do {
        for (int S = 0; S < (1<<n); S++) 
            if (check(id, S)) {cout << "Yes\n"; return 0;}  
    } while (next_permutation(id.begin() + 1, id.end()));
    cout << "No\n";
    return 0;
}
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

# E - Colorful Subsequence

# Question

有 NNN 个球排成一排。
左边的 iii 个球的颜色是 CiC_iCi​ ,数值是 ViV_iVi​ 。

高桥希望在不改变顺序的情况下,将这一行中的 KKK 个球移除,这样在排列剩余的球时,就不会有相邻的两个球颜色相同。此外,在此条件下,他希望最大化这一行中剩余球的总价值。

请计算高桥是否能移除 KKK 个球,使剩下的一行中没有相邻的两个球颜色相同。如果可以,求剩余球的最大总值。

  • 1≤K<N≤2×1051\leq K\lt N\leq 2\times 10^51≤K<N≤2×105
  • K≤500K\leq 500K≤500
  • 1≤Ci≤N1\leq C_i\leq N1≤Ci​≤N
  • 1≤Vi≤1091\leq V_i\leq 10^91≤Vi​≤109

# Solution

先考虑一种朴素的 DP,定义 dp[i][j][col]dp[i][j][col]dp[i][j][col] 表示前 iii 个球,以及移走了 jjj 个,末尾的最后一个球的颜色为 colcolcol 的最大值

考虑两种情况:

  • 移走第 iii 个球,那么转移方程为 dp[i][j][col′]=max⁡{dp[i−1][j−1][col′]}dp[i][j][col']=\max\{dp[i-1][j-1][col']\}dp[i][j][col′]=max{dp[i−1][j−1][col′]},其中 col′col'col′ 为上一次球的颜色
  • 不移走第 iii 个球,那么转移方程为 dp[i][j][col]=max⁡{dp[i−1][j][col′]+v[i]},c[i]≠col′dp[i][j][col]=\max\{dp[i-1][j][col']+v[i]\},c[i]\ne col'dp[i][j][col]=max{dp[i−1][j][col′]+v[i]},c[i]​=col′

这样的时间复杂度为 O(N2K)O(N^2K)O(N2K) 会超时

观察发现 dp[i][j−1][col]dp[i][j-1][col]dp[i][j−1][col] 的很多值都是空的,所以考虑值维护其最大值以及和最大值颜色不同的次大值,这样子每次转移肯定能从最大值和次大值里面挑一个转移,后面的小值就不需要去考虑了

所以我们修改一下定义

dp[i][j][p]dp[i][j][p]dp[i][j][p] 记录前 iii 个球,移走了 jjj 个,的最大值,次大值的 v[i]v[i]v[i] 总值和颜色

转移过程和朴素情况一样,只是当最大值和当前的 c[i]c[i]c[i] 相同时,改用次大值转移

这样的空间复杂度为 O(NK)O(NK)O(NK) 会超内存

发现 dp[i]dp[i]dp[i] 的状态只与 dp[i−1]dp[i-1]dp[i−1] 有关,所以考虑使用滚动数组把空间优化到了 O(K)O(K)O(K)

# Code

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll inf = 1e15;

int main() {
    freopen ("E.in", "r", stdin);
    int k ,n; cin >> n >> k;
    vector<int> c(n + 1), v(n + 1);
    for (int i = 1; i <= n; i++) 
        cin >> c[i] >> v[i];
    
    const vector<pll> infv = {{-inf, -1}, {-inf, -2}};
    vector<vector<vector<pll>>> dp(2);  // 三维数组 dp[i][j][col] 表示前 i 个物品中选了 j 个,且最后一个物品的颜色是 col 的最大价值
    dp[0].resize(k + 1, infv); dp[1].resize(k + 1, infv);
    dp[0][0][0].first = dp[0][0][1].first = 0;

    for (int i = 1; i <= n; i++) {
        const int col = c[i], val = v[i];
        auto &cur = dp[i & 1], &pre = dp[(i - 1) & 1];
        for (int j = 0; j <= k; j++)
            cur[j] = infv;
        
        //选了当前物品
        for (int j = 0; j <= k; j++) {
            for (auto &x : pre[j]) {
                const ll preval = x.first, precol = x.second;
                if (precol == col) continue;
                cur[j].push_back({preval + val, col});
                break;
            }
        }
        //没选当前物品
        for (int j = 1; j <= k; j++) {
            for (auto &x : pre[j - 1]) {
                const ll preval = x.first, precol = x.second;
                cur[j].push_back({preval, precol});
            }
        }

        //去重
        for (int j = 0; j <= k; j++) {
            auto &a = cur[j];
            sort(a.begin(), a.end()); reverse(a.begin(), a.end());
            if (a[0].second == a[1].second) {
                ll secval = -inf, seccol = -2;
                for (auto x : a) {
                    if (x.second != a[0].second) {
                        secval = x.first;
                        seccol = x.second;
                        break;
                    }
                }
                a[1] = {secval, seccol};
            }
            a.resize(2);
        }
    }

    ll ans = dp[n & 1][k][0].first;
    cout << (ans < 0 ? -1 : ans) << endl;
    return 0;
}
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

# F - Many Lamps

# Question

有一个简单的图,图中有 NNN 个顶点,编号为 111 至 NNN ,有 MMM 条边,编号为 111 至 MMM 。边 iii 连接顶点 uiu_iui​ 和 viv_ivi​ 。

每个顶点上都有一盏灯。初始时,所有的灯都是熄灭的。

请在 000 和 MMM 之间(包括首尾两次)执行以下操作,以确定是否可以恰好打开 KKK 盏灯。

  • 选择一条边。假设 uuu 和 vvv 是边的端点。切换 uuu 和 vvv 上的灯的状态。也就是说,如果灯亮着,则将其关闭,反之亦然。

如果可以恰好打开 KKK 盏灯,请打印实现该状态的操作序列。

# Solution

简化问题,整个图是连通的

有一个性质:开的灯的数量肯定是偶数,证明如下

每次对一条边进行操作:

  • 初始两个灯都是亮的,那么总亮灯数 −2-2−2
  • 初始一亮一暗,那么总亮灯数不变
  • 初始两个灯都是灭的,那么总亮灯数 +2+2+2

奇偶性不变,初始是 000 为偶数,所以亮的灯的数量总是偶数

考虑连通图的总数为 NNN ,设 XXX 为小于等于 NNN 的最大偶数,有一种构造方法能让 XXX 盏灯都点亮

  • 先建立连通图的生成树 GGG
  • 取 GGG 的一个叶节点 uuu,考虑与叶节点连接的其父亲节点 vvv
  • 如果 uuu 是灭灯状态的话,那么对 u−vu-vu−v 进行一次转换操作,如果 uuu 是亮灯的话则不操作
  • 删除 u−vu-vu−v 这条边

为什么这样是有效的,因为如果 uuu 是灭灯

  • vvv 也是灭灯,那么同时点亮了两盏灯,能使亮灯数增加
  • vvv 是亮灯,虽然亮灯数没有变大,但是能把 u−vu-vu−v 的亮灯状态进行调换,由于叶节点只连接父节点一盏灯,但父节点能连接很多其他灯,把亮的灯放到叶子节点,让父节点更有机会和别的节点进行亮两盏灯的操作

如果 K<XK<XK<X ,亮灯的过程是从 0∼X0\sim X0∼X 的连续偶数,当亮灯数 =X=X=X 时,中止过程即可

# Code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int main() {
    freopen ("F.in", "r", stdin);
    int n, m, k; cin >> n >> m >> k;
    vector<vector<pii> > g(n + 1);
    for (int i = 1; i <= m; i++) {
        int u,v; cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }

    int Y = 0;
    vector<int> ans, vis(n + 1, 0), cur(n + 1, 0);
    function<void(int)> dfs = [&](int u) {
        vis[u] = 1;
        for (auto [v, id] : g[u]) {
            if (vis[v]) continue;
            dfs (v);
            if (cur[v] == 0 && Y < k) { 
                Y -= cur[u] + cur[v];
                cur[u] ^= 1; cur[v] ^= 1;
                Y += cur[u] + cur[v];
                ans.push_back(id);
            }
        }
    };

    for (int i = 1; i <= n; i++) 
        if (!vis[i]) dfs(i);
    
    if (Y != k) cout << "No" << endl;
    else {
        cout << "Yes" << endl;
        cout << ans.size() << endl;
        for (auto x : ans) cout << x << " ";
        cout << endl;
    }
    return 0;
}
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

# G - Sugoroku 5

# Question

有一个棋盘游戏,其中有 N+1N+1N+1 个方格:方格 000 、方格 111 、方格 …\dots… 和方格 NNN 。
你有一个骰子,它能掷出一个介于 111 和 KKK 之间的整数,每种结果的概率相等。
您从 000 开始掷骰子。重复下面的操作,直到到达 NNN 格:

  • 掷骰子。假设 xxx 是当前方格, yyy 是掷出的数字,然后移动到方格 min⁡(N,x+y)\min(N, x + y)min(N,x+y) 。

假设 PiP_iPi​ 是经过恰好 iii 次操作后到达 NNN 个方格的概率。计算 P1,P2,…,PNP_1, P_2, \dots, P_NP1​,P2​,…,PN​ % 998244353998244353998244353

1≤K≤N≤2×1051 \leq K \leq N \leq 2 \times 10^51≤K≤N≤2×105

# Solution

假设 F(x)F(x)F(x) 是一次投掷筛子前进 nnn 格的生成函数

F(x)=1K∑i=1Kxi F(x) = \frac{1}{K} \sum_{i=1}^K x^i F(x)=K1​i=1∑K​xi

那么, kkk 掷完后, (0≤k<N)(0 \leq k \lt N)(0≤k<N) 位于方格的概率表示为 [xk]Fn[x^k] F^n[xk]Fn 。 nnn 掷出之后 (0≤k<N)(0 \leq k \lt N)(0≤k<N) 的概率表示为 [xk]Fn[x^k] F^n[xk]Fn 。因此, ana_nan​ ,即 nnn 掷出 (0≤n≤N)(0 \leq n \leq N)(0≤n≤N) 后没有达到目标的概率,可以表示为

an=∑k=0N−1[xk]Fn a_n = \sum_{k=0}^{N-1} [x^k] F^n an​=k=0∑N−1​[xk]Fn

那么,恰好投掷 nnn 次后达到目标的概率为 (1−an)−(1−an−1)=an−1−an(1-a_n)-(1-a_{n-1})=a_{n-1}-a_n(1−an​)−(1−an−1​)=an−1​−an​

所以只需要枚举 a0,a1,⋯,ana_0,a_1,\cdots,a_na0​,a1​,⋯,an​ 就可以知道答案

变换一下式子:

an=∑k=0N−1[xk]Fn=[xN−1](1+x+⋯+xN−1)Fn \begin{aligned} a_n &= \sum_{k=0}^{N-1} [x^k] F^n \\ &= [x^{N-1}] (1 + x + \dots + x^{N-1}) F^n \end{aligned} an​​=k=0∑N−1​[xk]Fn=[xN−1](1+x+⋯+xN−1)Fn​

考虑按照 KKK 的大小分类讨论

  1. KKK 比较大的情况:
an=[xN−1](1+x+⋯+xN−1)Fn=[xN−1](1+x+⋯+xN−1+xN+…)Fn=[xN−1]Fn1−x \begin{aligned} a_n &= [x^{N-1}] (1 + x + \dots + x^{N-1}) F^n \\ &= [x^{N-1}] (1+x+\dots+x^{N-1}+x^N+\dots) F^n \\ &= [x^{N-1}] \frac{F^n}{1-x} \end{aligned} an​​=[xN−1](1+x+⋯+xN−1)Fn=[xN−1](1+x+⋯+xN−1+xN+…)Fn=[xN−1]1−xFn​​
F(x)=1K∑i=1Kxi=x(1−xK)K(1−x) F(x) = \frac{1}{K} \sum_{i=1}^K x^i = \frac{x(1-x^K)}{K(1-x)} F(x)=K1​i=1∑K​xi=K(1−x)x(1−xK)​

在上面的表达式中得出

an=[xN−1]xn(1−xK)nKn(1−x)n+1=1Kn[xN−1−n](1−xK)n×1(1−x)n+1 \begin{aligned} a_n &= [x^{N-1}] \frac{x^n (1-x^K)^n}{K^n(1-x)^{n+1}} \\ &= \frac{1}{K^n} [x^{N-1-n}] (1-x^K)^n \times \frac{1}{(1-x)^{n+1}} \end{aligned} an​​=[xN−1]Kn(1−x)n+1xn(1−xK)n​=Kn1​[xN−1−n](1−xK)n×(1−x)n+11​​

考虑到 (1−xK)n(1-x^K)^n(1−xK)n 只在,0,K,2K,⋯0,K,2K,\cdots0,K,2K,⋯ 阶项中非零,则可以在 O(N/K)O(N/K)O(N/K) 的时间内求出 ana_nan​, a0∼aNa_0\sim a_Na0​∼aN​ 的时间复杂度为 O(N2/K)O(N^2/K)O(N2/K)

  1. KKK 比较小的情况
an=[xN−1](1+x+⋯+xN−1)Fn a_n = [x^{N-1}] (1 + x + \dots + x^{N-1}) F^n an​=[xN−1](1+x+⋯+xN−1)Fn

先考虑利用分治的方法求 ana_nan​

#include <iostream>
#include <vector>
using namespace std;

#include "atcoder/convolution.hpp"
#include "atcoder/modint.hpp"
using mint = atcoder::modint998244353;

int N, K;
vector<mint> f; // F = 1/K sum{i=1..K} x^i
vector<mint> a; // (a_0, a_1, ..., a_N)

// input  : l, r, g = (sum{i=0..N-1} x^i) F^l mod x^N
// output : F^{r-l} mod x^N
vector<mint> dc(int l, int r, vector<mint> g) {
  int b = g.size();
  if (l + 1 == r) {
    a[l] = g.back();
    return f;
  }
  int m = (l + r) / 2;
  auto p = dc(l, m, g);
  g = atcoder::convolution(g, p), g.resize(b);
  auto q = dc(m, r, g);
  auto res = atcoder::convolution(p, q);
  if ((int)res.size() > N) res.resize(N);
  return res;
}

int main() {
  cin >> N >> K;
  a.resize(N + 1);
  f.resize(K + 1);
  for (int i = 1; i <= K; i++) f[i] = mint{K}.inv();
  dc(0, N + 1, vector<mint>(N, 1));
  for (int i = 0; i < N; i++) cout << (a[i] - a[i + 1]).val() << "\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

总时间复杂度为 O(N2log⁡2N)O(N^2\log^2 N)O(N2log2N)

我们发现对于一个递归函数 dc(l,r,g)dc(l,r,g)dc(l,r,g) ggg 最多乘 FFF (r−l+1)(r-l+1)(r−l+1) 次,那么对于 ggg 中的小项,对答案没有影响

所以只需要保留最后的 K×(r−l+1)+1K\times (r-l+1)+1K×(r−l+1)+1 项即可

具体代码为:

  int b = min<int>(g.size(), (r - l - 1) * K + 1);
  g.erase(begin(g), begin(g) + g.size() - b);
1
2

这样就能在 O(NKlog⁡2N)O(NK\log^2 N)O(NKlog2N) 的时间复杂度下解决问题了

分界点取 K=N/log⁡NK=\sqrt{N}/\log NK=N​/logN

总时间复杂度为 O(N1.5log⁡N)O(N^{1.5}\log N)O(N1.5logN)

好像还有 O(Nlog⁡N)O(N\log N)O(NlogN) 的解法,但是我不会www

# Code

//https://atcoder.jp/contests/abc345/submissions/51423091
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl '\n'
using db = double;
template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<>>;
#include "atcoder/convolution.hpp"
#include "atcoder/modint.hpp"
using mint = atcoder::modint998244353;
int n, K, N;
const int D = ((db)sqrt(2e5) / (db)(log(2e5) / log(2)) + 1);
const int maxn = 3e5;
mint fac[maxn + 1], invfac[maxn + 1];
mint binom(int nn, int mm)  //求组合数 C(mm,nn)
{
	if (nn < mm)
		return 0;
	return fac[nn] * invfac[nn - mm] * invfac[mm];
};
void init()
{
	fac[0] = 1;
	for (int i = 1; i <= maxn; ++i)
		fac[i] = fac[i - 1] * i;
	invfac[maxn] = 1 / fac[maxn];
	for (int i = maxn - 1; i >= 0; --i)
		invfac[i] = invfac[i + 1] * (i + 1);
}
void solve1()
{
	vector<mint> f(n + 1);
	mint tot = 1;
	mint inv = 1, invK = mint{K}.inv();
	for (int i = 1; i <= n; ++i)
	{
		tot *= K;
		mint res = 0;
		inv *= invK;
		if (1LL * i * K < 1LL * n)
		{
			f[i] = 0;
			continue;
		}
		for (int j = 0; j <= i; ++j)
		{
			int sgn = (j % 2 == 0) ? 1 : -1;
			if (1LL * n - 1 - 1LL * j * (K) < 0)
				break;
			res += sgn * binom(i, j) * binom(n - 1 - j * (K), i);
		}
		f[i] = (tot - res) * inv;
	}
	for (int i = n; i >= 1; --i)
		f[i] -= f[i - 1];
	for (int i = 1; i <= n; ++i)
		cout << f[i].val() << endl;
}
vector<mint> a, f;
vector<mint> dc(int l, int r, vector<mint> g)
{
	int b = min<int>(g.size(), (r - l - 1) * K + 1); // 只保留最后 (r - l) * K 个
	g.erase(begin(g), begin(g) + g.size() - b);
	if (l + 1 == r)
	{
		a[l] = g.back();
		return f;
	}
	int m = (l + r) / 2;
	auto p = dc(l, m, g);
	g = atcoder::convolution(g, p), g.resize(b);
	auto q = dc(m, r, g);
	auto res = atcoder::convolution(p, q);
	if ((int)res.size() > N) res.resize(N);
	return res;
}
void solve2()
{
	a.resize(n + 1);
	f.resize(K + 1);
	for (int i = 1; i <= K; i++)
		f[i] = mint{K}.inv();
	dc(0, N + 1, vector<mint>(N, 1));
	for (int i = 0; i < n; i++)
		cout << (a[i] - a[i + 1]).val() << "\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> K;
	N = n;
	init();
	if (K > D)
		solve1();
	else
		solve2();
	return 0;
}
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
上次更新: 2025/04/08, 18:03:31
AtCoder Beginner Contest 344 A-G 题解
AtCoder Beginner Contest 346 A-G 题解

← AtCoder Beginner Contest 344 A-G 题解 AtCoder Beginner Contest 346 A-G 题解→

最近更新
01
计算机网络笔记
06-13
02
LLM101 NLP学习笔记
06-02
03
《python科学计算入门》学习笔记
05-30
更多文章>
Theme by Vdoing | Copyright © 2024-2025 Martian148 | MIT License
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式