ABC468-①C-DFS/托康展开②D-中心扩展③E-贡献法+逆元+前缀和#

https://www.wolai.com/3tQDqVUDZjQfGd14L8ppmE

C-DFS/康托展开#

题目#

给你一个整数 $N$ 和整数序列 $P=(P_1,P_2,\ldots, P_N)$ 和 $Q=(Q_1,Q_2,\ldots,Q_N)$ ，每个序列都是 $(1,2,\ldots,N)$ 的排列。

请问有多少个整数序列是 $(1,2,\ldots,N)$ 的置换序列，且其序数大于 $P$ ，小于 $Q$ 。

什么是整数序列的词序？

对于整数序列 $S = (S_1,S_2,\ldots,S_{|S|})$ 和 $T = (T_1,T_2,\ldots,T_{|T|})$ ，如果下面的 $1.$ 或 $2.$ 成立，我们就说 $S$ 在词典上小于 $T$ 。这里， $|S|, |T|$ 分别表示 $S, T$ 的长度。

$|S| \lt |T|$ 和 $(S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})$ 。
存在一个整数 $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ $1 \leq i \leq min {∣ S ∣, ∣ T ∣}$ ，使得以下两个条件都成立。
- $(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$
- $S_i$ 在数值上小于 $T_i$ 。

DFS#

排列型DFS

1
def dfs(n, p, q):
2
    used = [False] * (n + 1)
3
    ans = 0
4
    def dfs(pos, cur):
5
        nonlocal ans
6
        if pos == n:
7
            if p < cur < q:
8
                ans += 1
9
            return
10
        for num in range(1, n + 1):
11
            if not used[num]:
12
                if cur and cur < p[:pos] and cur > q[:pos]:
13
                    continue
14
                used[num] = True
15
                cur.append(num)
16
                dfs(pos + 1, cur)
17
                cur.pop()
18
                used[num] = False
19

20
    dfs(0, [])
21
    return ans
22
n = int(input())
23
p = list(map(int,input().split()))
24
q = list(map(int,input().split()))
25
print(dfs(n,p,q))

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

4
int dfs(int n, vector<int>& p, vector<int>& q) {
5
    vector<bool> used(n + 1, false);
6
    int ans = 0;
7

8
    function<void(int, vector<int>&)> dfs_impl = [&](int pos, vector<int>& cur) {
9
        if (pos == n) {
10
            if (cur > p && cur < q) {
11
                ans++;
12
            }
13
            return;
14
        }
15
        for (int num = 1; num <= n; num++) {
16
            if (!used[num]) {
17
                // 剪枝：如果前缀已经不可能在区间内
18
                bool prefix_ok = true;
19
                if (pos > 0) {
20
                    bool less_than_p = true, greater_than_q = true;
21
                    for (int k = 0; k < pos; k++) {
22
                        if (cur[k] >= p[k]) less_than_p = false;
23
                        if (cur[k] <= q[k]) greater_than_q = false;
24
                    }
25
                    if (less_than_p && greater_than_q) {
26
                        prefix_ok = false;
27
                    }
28
                }
29
                if (!prefix_ok) continue;
30

31
                used[num] = true;
32
                cur.push_back(num);
33
                dfs_impl(pos + 1, cur);
34
                cur.pop_back();
35
                used[num] = false;
36
            }
37
        }
38
    };
39

40
    vector<int> cur;
41
    dfs_impl(0, cur);
42
    return ans;
43
}
44

45
int main() {
46
    int n;
47
    cin >> n;
48
    vector<int> p(n), q(n);
49
    for (int i = 0; i < n; i++) cin >> p[i];
50
    for (int i = 0; i < n; i++) cin >> q[i];
51

52
    cout << dfs(n, p, q) << endl;
53
    return 0;
54
}

库函数#

使用permutations直接生成全排列

1
from itertools import permutations
2
n = int(input())
3
p = list(map(int, input().split()))
4
q = list(map(int, input().split()))
5
ans = 0
6
for a in permutations([i + 1 for i in range(n)]):
7
    ans += p < list(a) < q
8
print(ans)

康托展开#

定义

康托展开是一个双射，它将一个排列映射为一个整数，该整数表示该排列在所有排列中的字典序排名（从 0 开始）。

\text{rank} \in [0, N! - 1]

对于一个排列 $X = (X_1, X_2, \dots, X_N)$ ：

\text{rank}(X) = \sum_{i=1}^{N} a_i \times (N - i)!

其中 $a_i$ = 在 X[i] 后面出现的、比 X[i] 小的数的个数。

等价于：在当前未使用的数字中，有多少个比 X[i] 小的数。

1
def cantor_rank(X):
2
    N = len(X)
3
    fact = [1] * (N + 1)
4
    for i in range(1, N + 1):
5
        fact[i] = fact[i-1] * i
6

7
    rank = 0
8
    used = [False] * (N + 1)
9

10
    for i in range(N):
11
        # 统计未使用且小于 X[i] 的数字个数
12
        cnt = 0
13
        for num in range(1, X[i]):
14
            if not used[num]:
15
                cnt += 1
16

17
        rank += cnt * fact[N - i - 1]
18
        used[X[i]] = True
19

20
    return rank

把排列看作一个 N 位数字，每位可以选剩余未用的数字：

1
第1位：有 N 种选择 → rank 变化量 = 选第 k 小的数，跳过 (k-1) × (N-1)! 个排列
2
第2位：有 N-1 种选择 → rank 变化量 = 选第 k 小的数，跳过 (k-1) × (N-2)! 个排列
3
...

本质：康托展开就是计算”有多少个排列排在它前面”。

逆康托展开

给定 rank，还原排列：

1
def cantor_inverse(N, rank):
2
    fact = [1] * (N + 1)
3
    for i in range(1, N + 1):
4
        fact[i] = fact[i-1] * i
5

6
    available = list(range(1, N + 1))
7
    res = []
8

9
    for i in range(N):
10
        idx = rank // fact[N - i - 1]
11
        rank %= fact[N - i - 1]
12
        res.append(available.pop(idx))
13

14
    return res

排列哈希：将排列压缩为一个整数（ $0 \sim N!-1$ ）
排列的第 k 个：逆康托展开求排名第 k 的排列
区间计数：统计字典序在某区间的排列数
状态压缩：在 BFS/A* 中表示排列状态（如八数码问题）

1
MOD = 998244353
2
class Fenwick:
3
    def __init__(self, n):
4
        self.n = n
5
        self.bit = [0] * (n + 1)
6

7
    def add(self, idx, val):
8
        while idx <= self.n:
9
            self.bit[idx] += val
10
            idx += idx & -idx
11

12
    def sum(self, idx):
13
        res = 0
14
        while idx > 0:
15
            res += self.bit[idx]
16
            idx -= idx & -idx
17
        return res
18
def tuo_kang(a):
19
    n = len(a)
20
    fact = [1] * (n + 1)
21
    for i in range(1, n + 1):
22
        fact[i] = fact[i - 1] * i % MOD
23
    bit = Fenwick(n)
24
    for i in range(1, n + 1):
25
        bit.add(i, 1)
26
    rank = 0
27
    for i in range(n):
28
        cnt = bit.sum(a[i] - 1)  # 未使用且小于 a[i] 的个数
29
        rank = (rank + cnt * fact[n - i - 1]) % MOD
30
        bit.add(a[i], -1)  # 标记 a[i] 已使用
31
    return (rank + 1) % MOD
32
def main():
33
    n = int(input())
34
    a = list(map(int,input().split()))
35
    b = list(map(int,input().split()))
36
    print(tuo_kang(b) - tuo_kang(a) - 1 if tuo_kang(b) - tuo_kang(a) - 1 > 0 else 0)
37
if __name__ == "__main__":
38
    main()

D-中心扩展#

题目#

如果一个由小写英文字母组成的字符串满足以下条件，它就被称为好字符串。

它最多可以通过改写一个字符变成一个回文字符串。

例如，a、iwai和abcdcza是好字符串，但abcd和atcoder不是好字符串。特别要注意的是，重码字符串也是好字符串。

给您一个由小写英文字母组成的字符串 $S$ 。

请找出 $S$ 的非空子串（连续子序列）中有多少个是好字符串。

从 $S$ 的不同位置取出的两个子串即使作为字符串相等，也要分别计算。

什么是子串？

$S$ 的子串是删除 $S$ 开头的零个或多个字符和结尾的零个或多个字符后得到的字符串。例如，ab是abc的子串，但ac不是abc的子串。

中心扩展#

找出好字符串的中间字符在整个搜索中的位置。让这个中间字符成为第 $i$ 个字符。

中心为 $i$ 长度为 $2k+1$ 的子串是一个好字符串，这一事实等同于满足 $S_{i-j}\neq S_{i+j}$ 的 $j=1,2,\ldots,k$ 的个数小于 $1$ 。因此，只需确定在 $k$ 中升序为 $S_{i-j}\neq S_{i+j}$ 的 $1\le j\le k$ 的个数是否小于 $1$ 即可。用同样的方法可以确定偶数长度的好字符串的个数。

1
s = input().strip()
2
n = len(s)
3
ans = 0
4
for i in range(n):
5
    diff = 0
6
    l, r = i, i
7
    while l >= 0 and r < n:
8
        if s[l] != s[r]:
9
            diff += 1
10
        if diff <= 1:
11
            ans += 1
12
        else:
13
            break
14
        l -= 1
15
        r += 1
16
for i in range(n - 1):
17
    diff = 0
18
    l, r = i, i + 1
19
    while l >= 0 and r < n:
20
        if s[l] != s[r]:
21
            diff += 1
22
        if diff <= 1:
23
            ans += 1
24
        else:
25
            break
26
        l -= 1
27
        r += 1
28
print(ans)

1
s = input()
2
n = len(s)
3
ans = 0
4
for k in range(2):
5
    for st in range(n):
6
        l,r = st - k,st
7
        cnt = 0
8
        while 0 <= l and r < n:
9
            if s[l] != s[r]:
10
                cnt += 1
11
                if cnt == 2:
12
                    break
13
            l -= 1
14
            r += 1
15
            ans += 1
16
print(ans)

E-贡献法+逆元+前缀和#

题目#

给定序列 A，定义 $f(l, r)$ 为子数组 A[l..r] 的算术平均值。

求所有子数组的平均值之和，答案对 998244353 取模。

贡献法+逆元+前缀和#

交换求和顺序

原问题：

\sum_{l=1}^N \sum_{r=l}^N f(l, r) = \sum_{l=1}^N \sum_{r=l}^N \frac{\sum_{k=l}^r A_k}{r - l + 1}

考虑每个 A[i] 对答案的贡献：

\text{答案} = \sum_{i=1}^N A_i \times \left( \sum_{l=1}^i \sum_{r=i}^N \frac{1}{r - l + 1} \right)

括号内的部分记为 coeff[i]，即位置 i 的贡献系数。

coeff[i] = \sum_{l=1}^i \sum_{r=i}^N \frac{1}{r - l + 1}

令子数组长度 k = r - l + 1：

左端点 l 范围：max(1, i - k + 1) 到 min(i, N - k + 1)
长度 k 范围：1 到 N

coeff[i] = 所有包含 i 的子数组的 $\frac{1}{len}$ 之和。

前缀和优化

定义：

inv[k]：k 的模逆元
S[x] = inv[1] + inv[2] + ... + inv[x]

则对于固定的 l 和 r：

\frac{1}{r - l + 1} = inv[r - l + 1]

coeff[i] = $\sum_{l=1}^i \sum_{r=i}^N inv[r - l + 1]$

二重前缀和

令 pref[i] = S[1] + S[2] + ... + S[i]（S 的前缀和）

经过推导：

coeff[i] = pref[N] - pref[N - i] - pref[i - 1]

（其中 pref[0] = 0）

\text{答案} = \sum_{i=1}^N A_i \times coeff[i] \pmod{998244353}

预处理逆元 inv[1..N]
前缀和 S[1..N]
二重前缀和 pref[1..N]
遍历 i，计算 coeff[i] = pref[N] - pref[N-i] - pref[i-1]
累加 A[i] * coeff[i]

1
MOD = 998244353
2
n = int(input())
3
a = list(map(int, input().split()))
4
inv = [0] * (n + 1)
5
inv[1] = 1
6
for i in range(2, n + 1):
7
    inv[i] = MOD - MOD // i * inv[MOD % i] % MOD
8
s = [0] * (n + 1)
9
for i in range(1, n + 1):
10
    s[i] = (s[i - 1] + inv[i]) % MOD
11
pre = [0] * (n + 1)
12
for i in range(1, n + 1):
13
    pre[i] = (pre[i - 1] + s[i]) % MOD
14
ans = 0
15
for i in range(n):
16
    dif = (pre[n] - pre[n - i - 1] - pre[i]) % MOD
17
    ans = (ans + a[i] * dif) % MOD
18
print(ans)

音乐

音乐

ABC468-①C-DFS/托康展开②D-中心扩展③E-贡献法+逆元+前缀和#

C-DFS/康托展开#

题目#

DFS#

库函数#

康托展开#

D-中心扩展#

题目#

中心扩展#

E-贡献法+逆元+前缀和#

题目#

贡献法+逆元+前缀和#

文章分享

音乐

目录

音乐

音乐

[算法训练] ABC468-①C-DFS/托康展开②D-中心扩展③E-贡献法+逆元+前缀和

ABC468-①C-DFS/托康展开②D-中心扩展③E-贡献法+逆元+前缀和#

C-DFS/康托展开#

题目#

DFS#

库函数#

康托展开#

D-中心扩展#

题目#

中心扩展#

E-贡献法+逆元+前缀和#

题目#

贡献法+逆元+前缀和#

文章分享

音乐

目录