Lotuses's Blog

Easy 的题 题解

  • ~1.76K 字

如题目名字，这是一道简单的题。观察式子，

Missing or unrecognized delimiter for \Big \Big{\sum_{k_i\geq 0,(\sum_{i=1}^n k_i)=k} \Big[\frac{k!}{\prod_{i=1}^n(k_i!)}\cdot\prod_{i=1}^n(i!)^{k_i}\Big]\Big} \bmod p

就是
Missing or unrecognized delimiter for \Big \Big{\sum_{k_i\geq 0,(\sum_{i=1}^n k_i)=k} \Big[\binom{k}{k_1,k_2,\cdots,k_n}\cdot\prod_{i=1}^n(i!)^{k_i}\Big]\Big} \bmod p

利用多项式定理可以化简得，

再把 搞进去，就成了这样：

这时候，首先，时间复杂度可以变为 ，此时可以拿到 分。加上快速幂可以变为 。

还有阶乘的递推关系可以降到 。

现在解决如何处理 。由于 ，必须要优化。观察到当 时，对式子的贡献为 。所以，可以化为

此时最坏时间复杂度为 。又因为 ，可以咔过。

另外，因为只保证 ，所以模数 可能 ，long long 会爆掉，只能用 __int128 或高精（

所以，Solution：

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
#include <bits/stdc++.h>
#define int unsigned __int128
using namespace std;

int kpow(int a, int b, int mod) {
    int ans = 1, base = a % mod;
    do
    {
        if (b & 1) ans *= base, ans %= mod;
        base *= base; base %= mod;
    } while (b >>= 1);
    return ans;
}

#define gc getchar()
#define isd(ch) (ch >= '0' && ch <= '9')
template <typename T>
void read(T &r) {
    r = 0; char ch = gc, last = 'z';
    while (!isd(ch)) last = ch, ch = gc;
    while (isd(ch)) r = (r << 1) + (r << 3) + (ch ^ 48), ch = gc;
    if (last == '-') r = -r;
}

#define pc(ch) putchar(ch)
signed _buf[500], _len;
template <typename T>
void write(T w)
{
    _len = 0;
    if (w < 0) w = -w, pc('-');
    do _buf[_len++] = w % 10; while (w /= 10);
    for (signed i = _len - 1; i >= 0; i--)
        pc(_buf[i] + '0');
}

signed main() {
    int n, k, p, ans1 = 0, ans2 = 1, f = 1;
    read(n), read(k), read(p);
    for (int i = 1; i <= min(n, p - 1); i++)
        f *= i, f %= p, ans1 += f, ans1 %= p;
    ans2 = kpow(ans1, k, p);
    write(ans2);
    pc('\n');
    return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可