AtCoder Regular Contest 178 A~D

A.Good Permutation 2（贪心）

题意：

给你一个正整数 $N$ 和一个由 $M$ 个正整数 $A=(A_{1},A_{2}, \dots,A_{M})$ 组成的序列。

在这里， $A$ 的所有元素都是介于 $1$ 和 $N$ 之间的不同整数。

对于所有整数 $i$ （ $1\leq i\leq M$ ）满足以下条件时， $(1,2,\dots,N)$ 的排列 $P=(P_{1},P_{2},\dots,P_{N})$ 称为好排列：

$P$ 的任何连续子序列都不是 $(1,2,\dots,A_{i})$ 的置换。

判断是否存在好的排列，如果存在，求字典序最小的好的排列。

分析：

本题考虑贪心思维。

将答案数组赋初值为 $1, 2, ..., n$ ，将约束条件 $a_i$ 从小到大排序。

对于每一个 $x\in a$ ，因为每一个排列必须包含 $1$ ，所以就让 $res_1,res_2...,res_x$ 不是一个排列。

每次交换 $res_x$ 和 $res_{x+1}$ 可以保证符合要求，且字典序最小。

考虑无解的情况。

如果 $a = n$ ，则对于整个答案排列，一定是一个不符合这一要求的。
如果 $a = 1$ ，则对于答案中子序列{1}，同样无法满足。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1000005;
int a[N], b[N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> a[i];
    sort(a + 1, a + 1 + m);
    if (a[m] == n || a[1] == 1) {
        cout << "-1" << endl;
        return 0;
    }
    set<int> st;
    for (int i = 1; i <= n; i++)
        st.insert(i);
    for (int i = 1; i <= m; i++) {
        b[a[i]] = a[i] + 1;
        st.erase(a[i] + 1);
    }
    for (int i = 1; i <= n; i++) {
        if (b[i] == 0) {
            b[i] = *st.begin();
            st.erase(st.begin());
        }
    }
    for (int i = 1; i <= n; i++)
        cout << b[i] << " ";
    cout << endl;
    return 0;
}

B.1 + 6 = 7（数学）

题意：

给你正整数 $A_{1},A_{2},A_{3}$ 。求满足以下所有条件的正整数 $X_{1},X_{2},X_{3})$ 元组的个数，答案对 $998244353$ 取模。

$X_{1}$ 是一个十进制符号为 $A_{1}$ 位的正整数。
$X_{2}$ 是一个十进制符号为 $A_{2}$ 位的正整数。
$X_{3}$ 是一个十进制符号为 $A_{3}$ 位的正整数。
$X_{1}+X_{2}=X_{3}$ 。

每个输入给出 $T$ 个测试样例，请逐一求解。

分析：

令 $f(B_{1},B_{2},B_{3})$ 表示下面证明的答案。

考虑有多少对整数 $Y_{1},Y_{2})$ 满足以下所有条件？

$10^{B_{1}}\leq Y_{1}$
$10^{B_{2}}\leq Y_{2}$
$Y_{1}+Y_{2}\lt 10^{B_{3}}$

我们要找出满足以下所有条件的整数对 $X_{1},X_{2})$ 的个数：

$10^{A_{1}-1}\leq X_{1}$
$10^{A_{2}-1}\leq X_{2}$
$X_{1}+X_{2}\lt 10^{A_{3}}$
$10^{A_{1}}\leq X_{1}$ 不成立。
$10^{A_{2}}\leq X_{2}$ 不成立。
$X_{1}+X_{2}\lt 10^{A_{3}-1}$ 不成立。

利用包含-排除原则，这个问题的答案可以用 $f$ 表示如下：
$\sum_{i=0}^{1}\sum_{j=0}^{1}\sum_{k=0}^{1}f(A_{1}-i,A_{2}-j,A_{3}-k)(-1)^{i+j+k}$

因此，只需实现一个能快速计算 $f(B_{1},B_{2},B_{3})$ 的函数即可。对于 $f(B_{1},B_{2},B_{3})$ ，以下条件成立：

若 $B_{3}\leq\max(B_{1},B_{2})$ ，则 $f(B_{1},B_{2},B_{3})=0$ 。
若 $B_{3}\gt \max(B_{1},B_{2})$ ，则 $f(B_{1},B_{2},B_{3})= \dfrac{(10^{B_{3}}-10^{B_{1}}-10^{B_{2}})(10^{B_{3}}-10^{B_{1}}-10^{B_{2}}+1)}{2}$ 。

由上可知， $f(B_{1},B_{2},B_{3})$ 可在 $O(\log(B_{3}))$ 时间内计算，因此每个测试样例可在 $O(\log(A_{3}))$ 时间内解决此问题。

代码：

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/modint>
using mint = atcoder::modint998244353;
mint ten = 10;

mint f(int b1, int b2, int b3){
    if (max(b1, b2) >= b3) return 0;
    mint tmp = ten.pow(b3) - ten.pow(b1) - ten.pow(b2);
    return tmp * (tmp + 1) / 2;
}

int main(){
    int T;
    cin >> T;
    while(T--){
        int a1, a2, a3;
        cin >> a1 >> a2 >> a3;
        mint ans = 0, pm = 1;
        for (int i = 0; i < 2; i++){
            for (int j = 0; j < 2; j++){
                for (int k = 0; k < 2; k++){
                    ans += pm * f(a1 - i, a2 - j, a3 - k);
                    pm *= -1;
                }
                pm *= -1;
            }
            pm *= -1;
        }
        cout << ans.val() << endl;
    }
}

C.Sum of Abs 2（数学、动态规划）

题意：

问题陈述

给你正整数 $N$ 和 $L$ 以及长度为 $N$ 的正整数序列 $A=(A_{1},A_{2},\dots,A_{N})$ 。

就每个 $i=1,2,\dots,N$ 回答下面的问题：

判断是否存在一个由 $L$ 个非负整数 $B=(B_{1},B_{2},\dots,B_{L})$ 组成的序列，使得 $\displaystyle\sum_{j=1}^{L-1}\sum_{k=j+1}^{L}|B_{j}-B_{k}|=A_{i}$ 。如果存在，求该序列 $\max(B)$ 的最小值 $B$ 。

分析：

本题"绝对值之和"指的是以下公式：

$\sum_{j=1}^{L - 1}\sum_{k = j + 1} ^ {L} |B_{j} - B_{k}|$

当存在 $B$ 时，能够最小化 $\max(B)$ 的 $B$ 满足以下两个条件：

$B$ 按升序排序。
$B_{1}=0$ .

第一个条件成立的原因是，绝对值之和与 $B$ 的顺序无关。第二个条件成立是因为如果 $B$ 中的所有元素都是正数，那么从所有元素中减去 $1$ 就可以减少 $\max(B)$ 而不改变绝对值之和。

当 $B$ 按升序排序时，绝对值之和可以表示如下：

$\sum_{j=1}^{L-1}\sum_{k=j+1}^{L}|B_{j}-B_{k}|=\sum_{j=1}^{L-1}\sum_{k=j+1}^{L}(B_{k}-B_{j})=\sum_{k=1}^{L-1}k(L-k)(B_{k+1}-B_{k})$

这个变换是正确的，因为满足 $1\leq b\lt a\leq L$ 的整数 $a, b$ 为 $B_{a}-B_{b}=(B_{a}-B_{a-1})+(B_{a-1}+B_{a-2})+\cdots+(B_{b+1}-B_{b})$ ，满足 $b\leq k$ 和 $k+1\leq a$ 的整数对 $(a, b)$ 的个数为 $k (L - k)$ 。

如果我们让 $C_{k}=B_{k+1}-B_{k}$ ，那么当 $B$ 按升序排序和 $B_{1}=0$ 时，下面的情况成立：

$0\leq C_{k}$ .
绝对值之和等于 $\displaystyle\sum_{k=1}^{L-1}k(L-k)C_{k}$ 。
$\displaystyle\max(B)=B_{L}=\sum_{k=1}^{L-1}C_{k}$ .

因此，我们需要解决下面的问题：

确定是否存在长度为 $L - 1$ 的非负整数序列 $C$ ，使得 $\displaystyle\sum_{k=1}^{L-1}k(L-k)C_{k}=A_{i}$ ，如果存在，求这样的 $C$ 的最小和。

这个问题可以用动态规划的思想来解决，方法与背包问题相同，可以同时计算所有 $i$ 的和。

由于 $C_{k}=0$ 对于满足 $\max(A)\lt k(L-k)$ 的 $k$ 总是成立的，解法的空间复杂度为 $O(\max(A))$ ，时间复杂度为 $O(N+\max(A)\sqrt{\max(A)})$ 。

代码：

#include<bits/stdc++.h>

using namespace std;

int main() {
    int N, L;
    cin >> N >> L;
    const int S = 200200;
    vector<int> dp(S, S);
    dp[0] = 0;
    for (int k = 1; k < L; k++) {
        int w = k * (L - k);
        if (S < w)
            break;
        for (int i = 0; i + w < S; i++) {
            dp[i + w] = min(dp[i + w], dp[i] + 1);
        }
    }
    while (N--) {
        int a;
        cin >> a;
        cout << (dp[a] == S ? -1 : dp[a]) << endl;
    }
    return 0;
}

D.Delete Range Mex（动态规划）

题意：

给你一个正整数 $N$ 和一个由 $M$ 非负整数 $A=(A_{1},A_{2},\dots,A_{M})$ 组成的序列。

在这里， $A$ 的所有元素都是介于 $0$ 和 $N - 1$ 之间的不同整数。

求满足以下条件的 $(0,1,\dots,N-1)$ 的排列 $P$ 对 $998244353$ 取模的个数。

将序列 $B=(B_{1},B_{2},\dots,B_{N})$ 初始化为 $P$ 后，重复下面的操作若干次，可以得到 $B = A$ ：
- 选择 $l$ 和 $r$ ，使得 $1\leq l\leq r\leq|B|$ ，如果 $B$ 中包含 $\mathrm{mex}(\{B_{l},B_{l+1},\dots,B_{r}\})$ ，则将其从 $B$ 中删除。

$\mathrm{mex}(X)$ ：对于非负整数的有限集合 $X$ 来说， $\mathrm{mex}(X)$ 的定义是不在 $X$ 中的最小非负整数。

分析：

首先，让我们考虑是否有可能将 $B = P$ 转换为 $B = A$ 。由于 $B$ 中没有重复的元素，一旦从 $B$ 中删除了一个整数 $x$ ，之后就不可能再删除任何大于或等于 $x$ 的数字了。因此，我们需要按降序移除 $A$ 中不包含的元素。

此外，从 $B$ 中移除 $x$ 时，我们应该选择不包含 $x$ 且其 $\mathrm{mex}$ 为 $x$ 的最大区间。由于 $B$ 中没有重复的元素，因此最多有两个候选区间，我们应该选择包含所有小于 $x$ 的元素的区间。

最后，我们需要计算满足以下所有条件的 $P$ 的个数：

$A$ 作为 $P$ 的子序列存在。
对于所有不包含在 $A$ 中且介于 $0$ 和 $N - 1$ 之间的整数 $x$ ，以下条件之一成立：
- 从 $0$ 到 $x - 1$ 的所有整数的索引都小于 $x$ 的索引。
- 从 $0$ 到 $x - 1$ 的所有整数的索引都大于 $x$ 的索引。

我们考虑按升序插入不包含在 $A$ 中的整数来满足条件。

第一个条件总是满足的。

对于第二个条件，当插入一个整数 $x$ 时，我们应将其插入最左边小于 $x$ 的整数的左边，或插入最右边小于 $x$ 的整数的右边。

在此基础上，我们考虑动态规划。

设 $d p [i] [l] [r]$ 是插入 $i$ 以内整数的方法数，使得最左边整数的左边最多有 $l$ 个整数 $i$ ，最右边整数的右边最多有 $r$ 个整数 $i$ 。

问题的答案是 $d p [N - 1] [0] [0]$ 。

如果 $0$ 包含在 $A$ 中，则使用 $k$ 初始化 $d p [0] [k - 1] [M - k] = 1$ ，从而得到 $A_k=0$ 。

如果 $0$ 不包含在 $A$ 中，则初始化 $d p [0] [i] [M - i] = 1$ 为 $i=0,1,\dots,M$ 。

依次计算 $i=1,2,\dots,N-1$ 的 $d p [i]$ 。

当 $i$ 包含在 $A$ 中时

使用 $k$ 这样的 $A_k=i$ ，对所有 $l, r$ 进行如下更新：

$dp[i][\min(l,k-1)][\min(r,M-k)]+=dp[i-1][l][r]$

更新只需 $O(M^2)$ 时间。

当 $i$ 不包括在 $A$ 中时

以下条件成立：

$dp[i][l][r]=\sum_{L=l}^{M}dp[i-1][L][r] +\sum_{R=r}^{M}dp[i-1][l][R]$

如果用简单的方法计算，时间复杂度为 $O(M^3)$ ，但使用累积和方法，计算时间为 $O(M^2)$ 。

因此，我们的解决方案的总体时间复杂度为 $O(NM^2)$ 。
使用二项式系数直接计算 $d p [min (A)]$ 可以减少需要考虑的表的范围，从而使计算速度提高一个常数量级。

代码：

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

using mint = atcoder::modint;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> B(N, -1);
    for (int i = 0; i < M; i++) {
        int a;
        cin >> a;
        B[a] = i;
    }
    vector<mint> fact(N + 1, 1), fact_inv(N + 1, 1);
    for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i;
    fact_inv[N] = fact[N].inv();
    for (int i = N; i > 0; i--) fact_inv[i - 1] = fact_inv[i] * i;
    auto Binom = [&](int a, int b) -> mint {
        if (N < a || a < b || b < 0) return 0;
        return fact[a] * fact_inv[b] * fact_inv[a - b];
    };
    int X = 0;
    while (B[X] == -1) X++;
    int L = B[X], R = M - 1 - B[X];
    vector dp(L + 1, vector<mint>(R + 1));
    for (int i = 0; i <= L; i++)
        for (int j = 0; j <= R; j++) {
            int Y = X;
            if (i != L) Y--;
            if (j != R) Y--;
            int Z = L - i + R - j + 1;
            dp[i][j] = Binom(Y + Z, Z);
        }
    for (int idx = X + 1; idx < N; idx++) {
        int c = B[idx];
        if (c == -1) {
            vector n_dp(L + 1, vector<mint>(R + 1));
            for (int i = 0; i <= L; i++) {
                mint tmp = 0;
                for (int j = R; j >= 0; j--) {
                    tmp += dp[i][j];
                    n_dp[i][j] = tmp;
                }
            }
            for (int i = L; i >= 0; i--) {
                for (int j = 0; j <= R; j++) {
                    if (i) dp[i - 1][j] += dp[i][j];
                    n_dp[i][j] += dp[i][j];
                }
            }
            swap(n_dp, dp);
        } else if (c < L) {
            for (int i = c + 1; i <= L; i++) {
                for (int j = 0; j <= R; j++) {
                    dp[c][j] += dp[i][j];
                }
            }
            L = c;
        } else if (M - 1 - c < R) {
            c = M - 1 - c;
            for (int i = 0; i <= L; i++) {
                for (int j = c + 1; j <= R; j++) {
                    dp[i][c] += dp[i][j];
                }
            }
            R = c;
        }
    }
    cout << (dp[0][0] * (mint(2)).pow(max(X - 1, 0))).val() << endl;
    return 0;
}