pe-0873

user

带间隔的单词
记W(p,q,r)为由p个A、q个B和r个C构成、且任意A和B之间间隔至少两个C的单词数目。例如，对于W(2,2,4)，CACACCBB是一个合法单词，而ACBCACBC不是。

已知W(2,2,4)=32，W(4,4,44)=13908607644。

求W(10^6,10^7,10^8), 并对1e9+7取余作为你的答案。

给出cpp代码实现

deepseek v4 fast

好的，我们先分析一下这个题目，然后我会给出C++代码。

题目分析

我们要计算符合如下条件的单词数量：

字母由 p 个 A、q 个 B、r 个 C 组成。
任意 A 和 B 之间至少有两个 C。

转换问题
由于 C 是用来“隔开”A 和 B 的，我们可以先安排 A 和 B，再插入 C。

第一步：A 与 B 的排列

如果我们先忽略 C 的数量限制，只安排 A 和 B，其实就是一个由 A、B 组成且长度为 p+q 的序列。

但是这个序列必须满足：A 与 B 相邻时（或者仅间隔很少的 C），必须有至少 2 个 C 隔开。

换句话说：

如果我们把 A 和 B 放到序列中，然后准备在它们之间插入 C。
对于 A 和 B 之间（相邻位置），要求至少有 2 个 C。
对于 A 和 A 或 B 和 B 之间，可以没有 C。

所以我们只需要在 不同字母相邻 的位置固定放入 2 个 C。

第二步：结构建模

可以这样建模：

先排列 A 和 B（共 p+q 个位置）。
找出排列中相邻但字母不同的间隔数量，设为 k。
每个这样的间隔必须分配至少 2 个 C，于是至少占用 2k 个 C。
剩余的 C 数量是 r - 2k，可以自由分配到序列的 p+q+1 个空隙中（包括开头前和结尾后）。

第三步：组合计数

对每一种 k：

从 A 和 B 的排列里选取满足“不同字母相邻数 = k”的排列数。
将剩余 C 自由分配到 p+q+1 个空隙中，方法是 星与棒 的组合数：
若剩余 r - 2k 个 C，放入 p+q+1 个空隙，方法数为：
[
\binom{r - 2k + (p+q+1) - 1}{(p+q+1) - 1} = \binom{r - 2k + p + q}{p+q}
]
前提是 r >= 2k，否则为 0。

第四步：排列 A 和 B 时有 `k` 个不同相邻对

这是经典的计数：

A 和 B 的排列可看成将序列分块成相同字母的连续段。
若总共有 s 个连续段，则不同相邻对数 = s - 1。
我们的问题变成：统计 A 和 B 排列中，连续段数为 s = k+1 的排列数。

对给定的 p、q，连续段数为 s：

若第一段是 A，则 A 占 ceil(s/2) 段，B 占 floor(s/2) 段，或反过来。
我们可以用“隔板法”将 p 个 A 分成若干非空段，q 个 B 同样。
组合公式：
- 分成 a 段：( \binom{p-1}{a-1} )
- 分成 b 段：( \binom{q-1}{b-1} )

根据首字母不同，有 2 种情况：

先 A：a = ceil(s/2), b = floor(s/2)
先 B：a = floor(s/2), b = ceil(s/2)

两种都有效，除非某种分段数为 0，此时对应项为 0（p 或 q = 0 时特殊处理）。

第五步：最终公式

对每个可能的 k：
[
ways(k) = [\text{排列A,B 且有 k 个不同相邻}] \times \binom{r - 2k + p + q}{p+q}
]
累加所有 k 即可。

第六步：大数模运算

题目要求对 1e9+7 取模，阶乘与逆元预计算可以快速求组合数。

p, q, r 可达到 1e8，但 p+q 最大只有 1.1e7，这个范围内的阶乘可以预处理。

注意 k 的范围：k ≤ min(p+q-1, r/2)。

第七步：C++ 实现

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

const long long MOD = 1000000007;

long long modpow(long long base, long long exp) {
    long long res = 1;
    while (exp) {
        if (exp & 1) res = res * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}

struct Combinatorics {
    vector<long long> fact, invfact;
    Combinatorics(int n) {
        fact.resize(n+1);
        invfact.resize(n+1);
        fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i % MOD;
        invfact[n] = modpow(fact[n], MOD-2);
        for (int i = n-1; i >= 0; i--) invfact[i] = invfact[i+1] * (i+1) % MOD;
    }
    long long comb(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * invfact[k] % MOD * invfact[n-k] % MOD;
    }
};

int main() {
    long long p = 1000000, q = 10000000, r = 100000000;
    int N = p + q; // 1.1e7
    Combinatorics C(N + r + 5); // 最大需要的组合数范围

    long long ans = 0;

    for (long long k = 0; k <= min(p+q-1, r/2); k++) {
        long long s = k + 1; // 连续段数
        long long waysAB = 0;
        // 先A
        long long a1 = (s+1)/2, b1 = s/2;
        if (a1 <= p && b1 <= q && a1 > 0 && b1 > 0)
            waysAB = (waysAB + C.comb(p-1, a1-1) * C.comb(q-1, b1-1)) % MOD;
        // 先B
        long long a2 = s/2, b2 = (s+1)/2;
        if (a2 <= p && b2 <= q && a2 > 0 && b2 > 0)
            waysAB = (waysAB + C.comb(p-1, a2-1) * C.comb(q-1, b2-1)) % MOD;
        // 特殊情况：某一种字母为0段（即全是一种字母）
        if (s == 1) {
            if (p == 0 && q > 0) waysAB = 1;
            else if (q == 0 && p > 0) waysAB = 1;
            else if (p > 0 && q > 0) waysAB = 0; // s=1 且两种都有不可能
        }
        long long remC = r - 2*k;
        if (remC < 0) continue;
        long long waysC = C.comb(remC + p+q, p+q);
        ans = (ans + waysAB * waysC) % MOD;
    }

    cout << ans << endl;
    return 0;
}

复杂度分析

预处理阶乘与逆元：O(p+q+r)。
循环次数 ≤ min(p+q, r/2) ≤ 1.1e7。
在 C++ 中，这个规模可行（注意内存和时间优化，可以分块预处理阶乘）。

这样，我们能准确计算出 W(10^6, 10^7, 10^8) 模 1e9+7 的结果。

fun fact

一道组合数学典题,不太需要解释.
枚举AB然后插C即可.