AtCoder ABC 242 题解

A T-shirt

排名前 \(A\) 可得 T-shirt

排名 \([A+1,B]\) 中随机选 \(C\) 个得 T-shirt

给出排名 \(X\) ，求得到 T-shirt 的概率

一个 if 即可

B Minimize Ordering

给一个字符串 \(S\) ，求 \(S\) 排列出的字典序最小的字符串

一个排序

C 1111gal password

给 \(n\) ，求出满足条件的 \(n\) 位数 \(X\) 个数 \(\;mod\;998244353\)

\(\forall i\in[1,n],\quad1\le X_i\le 9\)
\(\forall i\in[1,n),\quad|x_i-x_{i+1}\le 1|\)
设 \(f_{i,j}\) 表示到第 \(i\) 位且为 \(j\) 的方案数，转移显然，\(O(10n)\)

D ABC Transform

由 A,B,C 组成的字符串 \(S\) ，一次变换，A -> BC, B -> CA, C -> AB

记 \(S^{(i)}\) 表示 \(S\) 经过 \(i\) 次变换的字符串

\(Q\) 次询问，第 \(i\) 次询问 \(S^{(t_i)}\) 的第 \(k_i\) 个字符

\(Q\le 10^5\) ，\(t,k\le 10^{18}\)

相当于从满二叉树的某一个点找到根。

就是一个 while 往上跳，每次其实就是字符往后 1 或 2。开一个变量记录即可，\(O(Q\log k)\)

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long uLL;

typedef long double LD;

typedef long long LL;

typedef double db;

const int N = 100005;

int n, Ti;

char x[N];

int main() {

    scanf("%s%d", x + 1, &Ti);

    n = strlen(x + 1);

    for (LL a, b, c; Ti--; ) {

        scanf("%lld%lld", &a, &b);

        c = 0;

        while (a && b > 1) {

            if (!(b & 1)) ++c;

            ++c;

            b = b + 1 >> 1, a--;

        }

        c += a;

        printf("%c\n", char((x[b] - 'A' + c) % 3 + 'A'));

    }

}

E (∀x∀)

\(T\) 组数据，每次给长度为 \(n\) 的字符串 \(S\)

求长度为 \(n\) ，字典序小于 \(S\) 的回文串 \(X\) 的数量 \(\;mod\;998244353\)

\(T\le 250000, \sum n\le 10^6\)

回文只用构造一半，枚举前半部分 \(i\) ，若 \(X_i<S_i\) 则区间 \([i+1,mid]\) 可以任意填

最后看 \(X，S\) 前半部分相同是否满足条件，\(O(Tn)\)

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long uLL;

typedef long double LD;

typedef long long LL;

typedef double db;

const int N = 1000005;

const LL P = 998244353;

int Ti, n, mi;

char a[N];

LL ans, fac[N];

inline int chk() {

    for (int i = mi; i; i--) {

        if (a[i] > a[n - i + 1]) return 0;

        if (a[i] < a[n - i + 1]) return 1;

    }

    return 1;

}

int main() {

    fac[0] = 1;

    for (int i = 1; i <= 1000000; i++) fac[i] = fac[i - 1] * 26 % P;

    scanf("%d", &Ti);

    while (Ti--) {

        scanf("%d", &n);

        for (int i = 1; i <= n; i++) {

            a[i] = getchar();

            while (a[i] < 'A' || a[i] > 'Z') a[i] = getchar();

        }

        mi = n + 1 >> 1, ans = chk();

        for (int i = 1; i <= mi; i++) {

            (ans += 1ll * (a[i] - 'A') * fac[mi - i] % P) %= P;

        }

        printf("%lld\n", ans);

    }

}

F Black and White Rooks

\(B\) 个黑棋，\(W\) 个白棋，放在 \(n\times m\) 的棋盘上，

一个棋子在 \((i,j)\) 则第 \(i\) 行第 \(j\) 列都不能有与其颜色不同的棋子

相同颜色的棋没有区别

求放完所有棋子的方案数 \(\;mod\; 998244353\)

\(n,m\le 50,B,W\le 2500,B+W\le n\times m\)

设 \(f_{i,j,x}\) 为用 \(x\) 个棋子占 \(i\) 行 \(j\) 列的方案数，则

\(ans=\sum_{i=1}^{n}\sum_{j=1}^{n-i}\sum_{k=1}^m\sum_{l=1}^{m-k}\binom{n}{i}\binom{n-i}{j}\binom{m}{k}\binom{m-k}{l}\times f_{i,k,B}\times f_{j,l,W}\)

可在 \(O(n^2m^2)\) 内求出答案，考虑求 \(f_{i,j,k}\) ，有两种方法，都可以做到 \(O(n^2m^2)\)

dp

\(f_{n,m,x}\) 等于 \(\binom{n\times m}{x}\) 减去（刚好 \(i\) 行 \(j\) 列放了的方案数），

其中 \(1\le i\le n,1\le j\le m,(i,j)\ne(n,m)\)

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long uLL;

typedef long double LD;

typedef long long LL;

typedef double db;

const LL P = 998244353;

const int N = 1e5 + 5;

int n, m, B, W;

LL fac[N], inv[N], fi[N], ans;

LL f1[55][55], f2[55][55];

inline LL C(LL n, LL m) {

    if (n < 0 || m < 0 || n < m) return 0;

    return fac[n] * fi[m] % P * fi[n - m] % P;

}

inline void init(int X, LL f[55][55]) {

    for (int i = 1; i <= n; i++)

        for (int j = 1; j <= m; j++) {

            f[i][j] = C(i * j, X);

            for (int k = 1; k <= n; k++)

                for (int l = 1; l <= m; l++) {

                    if (i == k && j == l) continue;

                    (f[i][j] += P - C(i, k) * C(j, l) % P * f[k][l] % P) %= P;

                }

        }

}

int main() {

    fac[0] = fi[0] = 1;

    fac[1] = inv[1] = fi[1] = 1;

    for (int i = 2; i <= 100000; i++) {

        fac[i] = fac[i - 1] * i % P;

        inv[i] = (P - P / i) * inv[P % i] % P;

        fi[i] = fi[i - 1] * inv[i] % P;

    }

    scanf("%d%d%d%d", &n, &m, &B, &W);

    init(B, f1);

    init(W, f2);

    for (int i = 1; i <= n; i++)

        for (int j = 1; j <= n - i; j++)

            for (int k = 1; k <= m; k++)

                for (int l = 1; l <= m - k; l++)

                    (ans += C(n, i) * C(n - i, j) % P * C(m, k) % P * C(m - k, l) % P * f1[i][k] % P * f2[j][l] % P) %= P;

    printf("%lld", ans);

}

容斥原理

根据容斥原理，\(f_{n,m,x}=\sum (-1)^{i+j}\times\) （至少 \(i\) 行 \(j\) 列没有放的方案数）

即：

\[f_{n,m,x}=\sum_{i=0}^n\sum_{j=0}^m
(-1)^{i+j}\times\binom{n}{i}\times\binom{m}{j}\times\binom{(n-i)\times(m-j)}{x}
\]

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long uLL;

typedef long double LD;

typedef long long LL;

typedef double db;

const LL P = 998244353;

const int N = 1e5 + 5;

int n, m, B, W;

LL fac[N], inv[N], fi[N], ans;

LL f1[55][55], f2[55][55];

inline LL C(LL n, LL m) {

    if (n < 0 || m < 0 || n < m) return 0;

    return fac[n] * fi[m] % P * fi[n - m] % P;

}

inline void init(int X, LL f[55][55]) {

    for (int i = 1; i <= n; i++)

        for (int j = 1; j <= m; j++)

            for (int k = 0; k <= i; k++)

                for (int l = 0, v; l <= j; l++) {

                    v = 1;

                    if ((k + l) & 1) v = -1;

                    (f[i][j] += v * C(i, k) * C(j, l) % P * C((i - k) * (j - l), X) % P) %= P;

                    (f[i][j] += P) %= P;

                }

}

int main() {

    fac[0] = fi[0] = 1;

    fac[1] = inv[1] = fi[1] = 1;

    for (int i = 2; i <= 100000; i++) {

        fac[i] = fac[i - 1] * i % P;

        inv[i] = (P - P / i) * inv[P % i] % P;

        fi[i] = fi[i - 1] * inv[i] % P;

    }

    scanf("%d%d%d%d", &n, &m, &B, &W);

    init(B, f1);

    init(W, f2);

    for (int i = 1; i <= n; i++)

        for (int j = 1; j <= n - i; j++)

            for (int k = 1; k <= m; k++)

                for (int l = 1; l <= m - k; l++)

                    (ans += C(n, i) * C(n - i, j) % P * C(m, k) % P * C(m - k, l) % P * f1[i][k] % P * f2[j][l] % P) %= P;

    printf("%lld", ans);

}

G Range Pairing Query

\(n\) 个数 \(a_i\) ，每次询问 \([l,r]\) ，若其中数出现次数 \(c_i\) ，求 \(\sum\lfloor\dfrac{c_i}{2}\rfloor\)

莫队板题，略

Ex Random Painting

\(n\) 个格子初始为白色，\(m\) 个区间 \([L_i,R_i]\)，每次从 \(m\) 个区间内随机选出一个 \(x\)

将格子 \(L_x,L_x+1,\cdots,R_x\) 染成黑色，求将所有格子染成黑色的期望次数 \(\;mod\ 998244353\)

sol

part 1

设 \(f_i\) 为从 \(m\) 中选 \(i\) 个能覆盖区间 \([1,n]\) 的方案数。

则答案为 \(\sum_{i=0}^n (1-\dfrac{f_i}{\binom{m}{i}})\times \dfrac{m}{m-i}\)

为什么？

前面一半：从 \(m\) 个中选 \(i\) 个不覆盖 \([1,n]\) 的概率，即不能终止

后面一半：选剩下 \(m-i\) 中选出一个没有选过的期望次数

二者相乘：当前状态为选了 \(i\) 条边，合法的概率 \(\times\) 选一条未选过的边的期望，转移到状态 \(i+1\)

一直转移，得到答案

part 2

求 \(f_i\) ，先将线段双关键排序

考虑 \(dp_{i,j,k}\) 表示前 \(i\) 条线段，选出 \(k\) 条的并集为 \([1,j]\) 的方案数

目标：\(f_k=dp_{m,n,k}\)

\(j<L_i-1\) ， \(dp_{i,j,k}=dp_{i-1,j,k}\)

\(L_i-1\le j<R_i\) ， \(dp_{i,j,k}=dp_{i-1,j,k}\) ， \(dp_{i-1,j,k-1}\rightarrow dp_{i,R_i,k}\)

\(R_i\le j\) ，

\[\begin{aligned}
dp_{i,j,k}=\begin{cases}
dp_{i-1,j,k} & \left(k=0\right)\\
dp_{i-1,j,k-1}+dp_{i-1,j,k} & \left(0<k\right)
\end{cases}
\end{aligned}
\]

j 倒叙枚举，保证 \(j=R_i\) 和 \(L_i-1\le j<R_i\) 时不重复

可以在 \(O(nm^2)\) 的时间内解决

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long uLL;

typedef long double LD;

typedef long long LL;

typedef double db;

const int N = 405;

const LL P = 998244353;

int n, m, a[N], b[N];

struct rg { int l, r; } x[N];

inline bool cmp(rg A, rg B) {

    if (A.l ^ B.l) return A.l < B.l;

    return A.r < B.r;

}

LL fac[N], inv[N], fi[N], f[N][N][N], ans;

inline LL C(int n, int m) {

    if (n == m || !m) return 1;

    return fac[n] * fi[m] % P * fi[n - m] % P;

}

inline LL Pow(LL x, LL y) {

    register LL res = 1;

    for (; y; y >>= 1, x = x * x % P)

        if (y & 1) res = res * x % P;

    return res;

}

inline LL Inv(LL x) { return Pow(x, P - 2); }

int main() {

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i++) scanf("%d%d", &x[i].l, &x[i].r);

    sort(x + 1, x + m + 1, cmp);

    for (int i = 0; i < m; i++) a[i] = x[i + 1].l, b[i] = x[i + 1].r;

    fac[1] = inv[1] = fi[1] = 1;

    for (int i = 2; i <= m; i++) {

        fac[i] = fac[i - 1] * i % P;

        inv[i] = (P - P / i) * inv[P % i] % P;

        fi[i] = fi[i - 1] * inv[i] % P;

    }

    f[0][0][0] = 1;

    for (int i = 0; i < m; i++) {

        for (int j = n; ~j; j--) {

            for (int k = 0; k <= m; k++) {

                if (j < a[i] - 1) f[i + 1][j][k] = f[i][j][k];

                else if (j <= b[i]) {

                    f[i + 1][j][k] = f[i][j][k];

                    if (k) (f[i + 1][b[i]][k] += f[i][j][k - 1]) %= P;

                } else {

                    f[i + 1][j][k] = f[i][j][k];

                    if (k) (f[i + 1][j][k] += f[i][j][k - 1]) %= P;

                }

            }

        }

    }

    for (int i = 0; i <= m; i++) {

        (ans += (1 - f[m][n][i] * Inv(C(m, i)) % P + P) % P * m % P * Inv(m - i) % P) %= P;

    }

    printf("%lld", ans);

}

虚拟赛体验

第一场 AT 居然是虚拟赛

只写了 ABCEG ，发现其实 AT 是手速和思维一起的

比如比较 naive 的 D 由于时间没有打

以后便是开始线上赛了

virtual judge 当时是前 30 ？大雾

也是一个新的练习平台，新的开始，确信

AtCoder ABC 242 题解

AtCoder ABC 242 题解

A T-shirt

B Minimize Ordering

C 1111gal password

D ABC Transform

E (∀x∀)

F Black and White Rooks

dp

容斥原理

G Range Pairing Query

Ex Random Painting

sol

part 1

part 2

虚拟赛体验