跳转至

ABC171F

知识点

  • 组合数学
  • 快速幂
  • 容斥原理

题意简述

给定一个字符串 \(S\) 和数字 \(k\),求所有本质不同的字符串 \(T\) 的个数,使得 \(\left|T\right| = \left|S\right| + k\),且 \(S\)\(T\)子序列1

数据范围:\(1 \le \left|S\right|, k \le 10^6\)

解题思路

\(n = \left|S\right|, m = \left|S\right| + k\)

正着计算 \(S\)\(T\) 的子序列时 \(T\) 的个数不方便,因此我们可以考虑计算 \(S\) 不为 \(T'\)子序列\(T'\) 的个数。

再用 \(26^m\) 减去 \(T'\) 的个数,即为 \(T\) 的个数。

\(T'\) 中可能包含 \(S\) 的前缀 \(S[1], S[1..2], S[1..3], \cdots, S[1.. n - 1]\)

当然,也可能不包含 \(S\) 的任意一个前缀,可以看做包含 \(S[1\ldots0] = \epsilon\)

\(T'\) 包含 \(S[1.. i] \quad i \in [0, n)\) 时,从 \(m\) 个位置里选取 \(i\) 个位置来填这些字符有 \(\dbinom{m}{i}\) 种方法,

而要求剩下的 \(m - i\) 个位置不能包含 \(S[i + 1]\) 这个字母(因为包含了就会组成 \(S[1..i + 1]\) 这个子序列了),

因此有 \(25^{m - i}\) 种方法。

答案即为 $$ 26^{m}-\sum_{i = 0}^{n - 1}\binom{m}{i}\cdot25^{m - i} $$ 值得一提的是,此题的答案与 \(S\) 具体是什么无关,只与 \(\left|S\right|\) 有关。

代码实现

核心部分已用高亮标出。

Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
#define LL long long

const int mod = 1e9 + 7;
const int N = 1e6 + 5;
const int M = 2e6 + 5;

int n, k;
int m, fac[M] = { 1 }, inv[M];
char str[N];

LL tot, mis;

int mul(int ta, int tb) {
    int ret;
    __asm__ __volatile__ ("\tmull %%ebx\n\tdivl %%ecx\n":"=d"(ret):"a"(ta), "b"(tb), "c"(mod));
    return ret;
}

int qpow(int bas, int po) {
    int res = 1;
    while(po) {
        if(po & 1)
            res = mul(res, bas);
        bas = mul(bas, bas);
        po >>= 1;
    }
    return res;
}

int C(int tn, int tm) {
    return mul(fac[tn], mul(inv[tm], inv[tn - tm]));
}

int32_t main() {
    scanf("%d %s", &k, str + 1);
    n = strlen(str + 1);
    m = n + k;
    tot = qpow(26, m);
    for(int i = 1; i <= m; ++i)
        fac[i] = mul(fac[i - 1], i);
    for(int i = 0; i <= m; ++i)
        inv[i] = qpow(fac[i], mod - 2);
    for(int i = 0; i <= n - 1; ++i)
        mis = (mis + mul(C(m, i), qpow(25, m - i))) % mod;
    tot = ((tot - mis) % mod + mod) % mod;

    printf("%d", tot);

    return 0;
}

  1. 原题链接: F - Strivore