⟵ 这是一个博客 · Magic 的个人博客归档 | 分类 | 关于

CF794G 题解

2025 年 09 月 25 日

这题其实不难。

Update 2025.3.26：修改题解 Markdown。

Update 2025.3.27：修改题解中错误的式子，并重写逻辑清晰的代码。

Part 1.

首先，考虑没有 ? 如何做。

分两种情况：

字符串 $x$ 与 $y$ 长度相等。
字符串 $x$ 与 $y$ 长度不相等。

先考虑 $x$ 和 $y$ 长度不相等怎么做。

首先，将两个串中共同的字符删除。

比如 ABBAAA 和 BABBB，两个串有一个共同的 A，两个共同的 B，删除之后变为 AAA 和 BB。

那么显然，01 串 $s$ 与 $t$ 的长度比为 $2:3$

设 $s$ 为 $\overline{ab}$，$t$ 为 $\overline{cde}$，$a,b,c,d,e$ 为长度相等的 01 串。

替换一下 $x$ 和 $y$。

ABBAAA 变为 $\overline{abcdecdeababab}$。

BABBB 变为 $\overline{cdeabcdecdecde}$。

如果要让替换后的 01 串相等，那么我们需要保证 $a = b = c = d = e$。

如果我们多观察一下别的 $x$ 和 $y$，使用相同的步骤操作，我们会发现，若 $s$ 和 $t$ 长度最简比为 $a:b$，那么那么 $s = aE$，$t = bE$。

其中 $E$ 是一个 01 串。$kE$ 表示 $k$ 个 $E$ 拼接在一起。

由于 $s$ 和 $t$ 的长度限制是 $n$，那么 $E$ 的长度限制就是 $len = \lfloor\frac{n}{\max{a, b}}\rfloor$。

我们求出长度小于等于 $len$ 的非空 01 串即为这种情况的答案。

答案 $= 2^{len + 1} - 2$。

注意如果 $x$ 或者 $y$ 在删除共同字符之后为空，那么无解。

接下来考虑 $x$ 和 $y$ 长度相等怎么做。

这种情况还要再细分。

$x$ 和 $y$ 完全相等。

显然，$s$ 和 $t$ 可以任意取。

答案为 $(2^{n + 1} - 2)^2$。
$x$ 和 $y$ 中 A 的数量相等（并且 B 的数量相等）。

这种情况 $s$ 和 $t$ 的长度仍然是可以任取，但是由于 $x$ 和 $y$ 不相同，那么必然会有某些位置 $x_i =$ A，$y_i =$ B（或相反），那么 $s$ 和 $t$ 中必然会有一个串是另一个串的前缀。然后，举个例子，$s$ 长度为 $6$，$t$ 长度为 $4$。设 $s = \overline{abcdef}, t = \overline{abcd}$。

$\texttt{abcdef{\color{red}{abcd}}}$

$\texttt{abcd{\color{red}{abcd}}}$

标红是因为无论后面接上的是 $s$ 还是 $t$，前四个都一定是 $\overline{abcd}$。那么可以得出 $e = a, f = b, a = c, b = d$。

那么 $a = c = e$ 并且 $b = d = f$。

所以 $s = \overline{ababab}, t = \overline{abab}$。

简单证明或者感性理解即可得知：$s$ 和 $t$ 的最长重复单元长度为：$\gcd(\lvert s\rvert, \lvert t\rvert)$。

那么答案即为 $\sum\limits_{a = 1}^{n}\sum\limits_{b = 1}^{n}2^{\gcd(a, b)} = \sum\limits_{k = 1}^{n}(2^k(2\sum\limits_{j = 1}^{\lfloor\frac{n}{k}\rfloor}\varphi_j - 1))$（推式子见结尾）。

前缀和处理 $\sum\limits_{i = 1}^{\lfloor\frac{n}{k}\rfloor}\varphi_i$ 即可。
以上两种情况都不符合。

显然，对于这种情况，$s$ 一定等于 $t$。

那么答案为 $2^{m + 1} - 2$。

以上解决了无 ? 的情况。

Part 2.

现在解决有 ? 的情况。

分两种情况：

字符串 $x$ 与 $y$ 长度相等。
字符串 $x$ 与 $y$ 长度不相等。

还是先考虑 $x$ 和 $y$ 长度不相等怎么做。

首先，我们计算出 $x$ 与 $y$ 中含有的 A 和 B 的差。

设 $cnt_{x, A}$ 表示 $x$ 中 A 的个数，其他同理。

那么：记 A 个数差 $d_A = cnt_{x, A} - cnt_{y, A}$，B 个数差 $d_B = cnt_{x, B} - cnt_{y, B}$。

然后，我们考虑最边界的情况，$x$ 中的所有 ? 设为 A；$y$ 中的所有 ? 设为 B。

那么：

\[d_A = cnt_{x, A} - cnt_{y, A} + cnt_{x, ?}\] \[d_B = cnt_{x, B} - cnt_{y, B} - cnt_{y, ?}\]

接下来，我们考虑修改问号的值会发生什么。

举个例子：

$\texttt{AAB?B?A}$

$\texttt{B?ABBB?A}$

变为边界情况：

$\texttt{AAB{\color{red}{A}}B{\color{red}{A}}A}$

$\texttt{B{\color{red}{B}}ABBB{\color{red}{B}}A}$

接下来我们以这个状态为基准，我们发现，翻转任意一个标红字母（将 A 变为 B，或相反），对 $d_A$ 和 $d_B$ 的影响都是一样的。

将 $x$ 中的 A 变为 B，会导致 $d_B$ 加一，而 A 的数量减一，$d_A$ 减一。

若将 $y$ 中的 B 变为 A，同样会导致 $d_B$ 加一，$d_A$ 减一。

那么我们可以枚举有多少个字母从基准状态翻转了。

标红字母个数为 $cnt_?$，翻转字母数量为 $k$，那么总共可能的情况有 $C_{cnt_?}^{k}$ 种，$d_A’ = d_A - k$，$d_B’ = d_B + k$。

然后我们考虑每组 $d_A’$ 和 $d_B’$ 怎么计算贡献。

如果 $d_A’ \times d_B’ \ge 0$，那么则代表两者同号或有一项等于 $0$，那么就对应了这种情况：

注意如果 $x$ 或者 $y$ 在删除共同字符之后为空，那么无解。

只有两者异号，才能产生贡献。

然后两者异号，就可以直接用上面的无 ?、$x,y$ 不等长解决。

$s,t$ 长度最简比即为 $d_B’$ 与 $d_A’$ 的最简比。

设 $f_{a, b}$ 表示 $d_A’ = a$，$d_B’ = b$ 时的答案。

最终答案为：

\[\sum\limits_{i = 0}^{cnt_?}(C_{cnt_?}^{k}\times f_{d_A - i, d_B + i})\]

$f_{a, b}$ 直接求解，$O(\log n)$，$\log$ 来自快速幂和 $\gcd$。

总复杂度 $O(n \log n)$。

接下来考虑 $x,y$ 长度相等的情况。

我们需要先扫描一遍，判断是否有某种组合，让 $x = y$，如果有，计算出情况数 $cnt_s$（same）。

再计算出边界情况下的 $d_A$ 和 $d_B$。

接下来，我们如果需要让两个串 A 的数量相等，那么应当使 $d_A = 0$。

对应的情况数 $cnt_e$（equal）$= C_{cnt_?}^{d_A} - cnt_s$，要注意这种情况是严格包含 $cnt_s$ 的情况的，所以要减掉。

若 $d_A < 0$ 或 $d_A > cnt_?$，则 $cnt_e = 0$，因为不可能使两串 A 数量相等。

剩下的情况则为普通情况，数量 $cnt_n$（normal）$= 2^{cnt_?} - cnt_s - cnt_e$。

接下来我们一个个计算贡献。

same：相同则任意取：$(2^{n + 1} - 2)^2$。

equal：长度任意：$\sum\limits_{k = 1}^{n}(2^k(2\sum\limits_{j = 1}^{\lfloor\frac{n}{k}\rfloor}\varphi_j - 1))$。

normal：$s = t$，$(2^{n + 1} - 2)$。

最终答案为：

\[cnt_s\times(2^{n + 1} - 2)^2 + cnt_e \times \sum\limits_{k = 1}^{n}(2^k(2\sum\limits_{j = 1}^{\lfloor\frac{n}{k}\rfloor}\varphi_j - 1)) + cnt_n\times (2^{n + 1} - 2)\]

前缀和处理欧拉函数，复杂度 $O(n)$。

接下来讲一下一些式子。

在上面经常会看到 $2^{n + 1} - 2$ 出现。

这个即为长度小于等于 $n$ 的 01 串的数量。

因为 $\sum\limits_{i = 1}^{n} 2^i = 2^{n + 1} - 2$，小学数学即可证明。

$\sum\limits_{a = 1}^{n}\sum\limits_{b = 1}^{n}2^{\gcd(a, b)}$ $=\sum\limits_{k = 1}^{n}\sum\limits_{a|k}^{n}\sum\limits_{b|k}^{n}2^k[\gcd(a, b) = k]$ $=\sum\limits_{k = 1}^{n}\sum\limits_{i = 1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j = 1}^{\lfloor\frac{n}{k}\rfloor}2^k[\gcd(i, j) = 1]$ $=\sum\limits_{k = 1}^{n}2^k\sum\limits_{i = 1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j = 1}^{\lfloor\frac{n}{k}\rfloor}[\gcd(i, j) = 1]$

考虑这块的含义：$\sum\limits_{i = 1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j = 1}^{\lfloor\frac{n}{k}\rfloor}[\gcd(i, j) = 1]$。

这块即为数对 $(i, j)$，满足 $1\le i, j\le\lfloor\frac{n}{k}\rfloor$，且 $i, j$ 互质的个数。

首先，我们知道欧拉函数 $\varphi_i$ 表示 $1$ 到 $i$ 中与 $i$ 互质的数的个数。

那么我们先假定 $i < j$，那么显然数对个数为 $\sum\limits_{j = 2}^{\lfloor\frac{n}{k}\rfloor}\varphi_j$。

那么相反的情况：$i > j$，与上面相同。

然后就是 $i = j$，只有 $(1, 1)$ 符合，贡献为 $1$。

那么原式等于：

\[\sum\limits_{k = 1}^{n}2^k(1 + 2\sum\limits_{j = 2}^{\lfloor\frac{n}{k}\rfloor}\varphi_j)\] \[=\sum\limits_{k = 1}^{n}2^k(2\sum\limits_{j = 1}^{\lfloor\frac{n}{k}\rfloor}\varphi_j - 1)\]

AC 记录。

要注意取模、爆 long long。

这些都是因为取模和爆 long long WA 的。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N = 1000005, P = 1000000007;
string x, y;
int n;
int Gcd(int a, int b) {
    if(b == 0) return a;
    return Gcd(b, a % b);
}
int ksm(int a, int n) {
    if(n == 0) return 1;
    if(n == 1) return a % P;
    int d = ksm(a, n / 2);
    d = d * d % P;
    if(n & 1) d = d * a % P;
    return d;
}
int calc(int da, int db) {
    if(da * db >= 0) return 0;
    da = abs(da);
    db = abs(db);
    int gd = Gcd(da, db);
    int a = da / gd;
    int b = db / gd;
    int len = n / max(a, b);
    return (ksm(2, len + 1) - 2 + P) % P;
}
int frac[N], ifrac[N];
int phi[N];
int sumphi[N];
bool not_prime[N];
int plist[N], h;
int C(int n, int m) {
    return frac[n] * ifrac[n - m] % P * ifrac[m] % P;
}
void init() {
    frac[0] = 1;
    for(int i = 1; i < N; i ++) {
        frac[i] = frac[i - 1] * i % P;
    }
    ifrac[N - 1] = ksm(frac[N - 1], P - 2);
    for(int i = N - 2; i >= 0; i --) {
        ifrac[i] = ifrac[i + 1] * (i + 1) % P;
    }
    not_prime[1] = 1;
    phi[1] = 1;
    for(int i = 2; i < N; i ++) {
        if(!not_prime[i]) {
            phi[i] = i - 1;
            plist[++ h] = i;
        }
        for(int j = 1; j <= h && plist[j] * i < N; j ++) {
            not_prime[plist[j] * i] = 1;
            if(i % plist[j] == 0) {
                phi[plist[j] * i] = phi[i] * plist[j];
                break;
            }
            phi[plist[j] * i] = phi[plist[j]] * phi[i];
        }
    }
    for(int i = 1; i < N; i ++) {
        sumphi[i] = (sumphi[i - 1] + phi[i]) % P;
    }
    return ;
}
void diff() {
    int da = 0, db = 0;
    int cnt = 0;
    for(int i = 0; x[i]; i ++) {
        if(x[i] == 'A') da ++;
        if(x[i] == 'B') db ++;
        if(x[i] == '?') {cnt ++; da ++; }
    }
    for(int i = 0; y[i]; i ++) {
        if(y[i] == 'A') da --;
        if(y[i] == 'B') db --;
        if(y[i] == '?') {cnt ++; db --; }
    }
    int ans = 0;
    for(int k = 0; k <= cnt; k ++) {
        ans += C(cnt, k) * calc(da - k, db + k) % P;
        ans %= P;
    }
    printf("%d\n", ans);
    return ;
}
void same() {
    int cnts = 1, cnte = 0, cntn = 0;
    int da = 0, db = 0;
    int cnt = 0;
    for(int i = 0; x[i]; i ++) {
        if(x[i] == 'A') da ++;
        if(x[i] == 'B') db ++;
        if(x[i] == '?') {da ++; cnt ++; }
        if(y[i] == 'A') da --;
        if(y[i] == 'B') db --;
        if(y[i] == '?') {db --; cnt ++; }
        if(x[i] != y[i] && x[i] != '?' && y[i] != '?') {
            cnts = 0;
        } else if(x[i] == y[i] && x[i] == '?') {
            cnts *= 2;
            cnts %= P;
        }
    }
    cnte = (da < 0 || da > cnt) ? 0 : (C(cnt, da) - cnts + P) % P;
    cntn = (ksm(2, cnt) - cnts - cnte + 2 * P) % P;
    int sume = 0, pw = 1;
    for(int k = 1; k <= n; k ++) {
        pw = pw * 2 % P;
        sume += pw * ((2 * sumphi[n / k] % P - 1 + P) % P) % P;
        sume %= P;
    }
    int ans = {
        cnts * ksm((ksm(2, n + 1) - 2 + P) % P, 2) % P +
        cnte * sume +
        cntn * (ksm(2, n + 1) - 2 + P) % P
    } ;
    ans %= P;
    printf("%d\n", ans);
    return ;
}
signed main() {
    init();
    cin >> x >> y >> n;
    if(x.size() == y.size()) {
        same();
    } else {
        diff();
    }
    return 0;
}

声明

本博客主题参考了这位大佬的博客。

本文使用CC BY 4.0 协议。转载时请注明出处。