CF794G 题解

这题其实不难。

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(|s|, |t|)$ 。

那么答案即为 $\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, ?}

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

举个例子：

为方便染色，使用

\LaTeX

。

$\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 的。

代码

CPP

#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;
}

文章操作

Part 1.

Part 2.

代码

相关推荐

评论

CF794G 题解