洛谷P2000 拯救世界题解

题目链接：P2000 拯救世界

题意：

为了拯救世界，小 a 和 uim 决定召唤出 kkksc03 大神和 lzn 大神。根据古籍记载，召唤出任何一位大神，都需要使用金木水火土五种五行神石来摆一个特定的大阵。而在古籍中，记载是这样的：

kkksc03 大神召唤方法：

金神石的块数必须是 $6$ 的倍数；

木神石最多用 $9$ 块；

水神石最多用 $5$ 块；

火神石的块数必须是 $4$ 的倍数；

土神石最多用 $7$ 块。

lzn 大神召唤方法:

金神石的块数必须是 $2$ 的倍数；

木神石最多用 $1$ 块；

水神石的块数必须是 $8$ 的倍数；

火神石的块数必须是 $10$ 的倍数；

土神石最多用 $3$ 块。

现在是公元 $1999$ 年 $12$ 月 $31$ 日，小 a 和 uim 从 $00{:}00{:}00$ 开始找，一直找到 $23{:}00{:}00$，终于，还是没找到神石。

不过，他们在回到家后在自家地窖里发现了一些奇怪的东西，一查古籍，哎呦妈呀，怎么不早点来呢？这里有一些混沌之石，可以通过敲击而衰变成五行神石。于是，他们拼命地敲，终于敲出了 $n$ 块神石，在 $23{:}59{:}59$ 完成了两座大阵。

然而，kkksc03 大神和 lzn 大神确实出现了，但是由于能量不够，无法发挥神力。只有把所有用 $n$ 块神石可能摆出的大阵都摆出来，才能给他们充满能量。这下小 a 和 uim 傻了眼了，赶快联系上了你，让你帮忙算一下，一共有多少种大阵。

输入格式：

输入一个正整数 $n$。

输出格式：

输出用 $n$ 块混沌之石能摆出的大阵的种数。

数据范围：

对于全部数据，$10^{99999}\leq n\lt 10^{100000}$ ，除了样例。时限 500ms。

生成函数裸题。根据生成函数的思路，我们可以按以下方式构造函数。

例如：我们要求某种石头只能用 $6$ 的倍数个，则定义形式幂级数

$F_1(x) = 1 + x^6 + x^{12} + \cdots = \frac{1}{1-x^6}$

又比如，我们要求某种石头只能用不超过 $5$ 个，则定义函数

$F_2(x) = 1 + x^2 + x^3 + x^4 + x^5= \frac{1-x^6}{1-x}$

那么我们只需要按照题目把所有的函数都求出来，再乘起来就是 $(1-x)^{-5}$ 。

利用广义二项式定理展开它，则第 $n$ 项的系数就是我们要求的答案，显然

$\begin{aligned} \mathrm{Ans} &= \binom{-5}{n}\times (-1)^{-5-n} = (-1)^{-5}\binom{n + 5 - 1}{n}= \binom{n+4}{4} \\[6pt]&= \frac{1}{24}(n+1)(n+2)(n+3)(n+4) \end{aligned}$

注意这里 $n$ 钦定为了 $2^m$ ，这一点可以利用高位补 $0$ 做到。

至此题目就变成了三次 NTT 优化高精度加上一次高精除单精了，具体实现见代码。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1048576 + 15))

const int P = 998244353;
const int G = 3, Gi = 332748118;
int a[N], b[N], num[N];
int l, r[N], limit = 1, Inv;
int qpow(int a, int b)
{
    int r = 1;
    while(b)
    {
        if(b & 1) r = r * a % P;
        b >>= 1; a = a * a % P;
    }
    return r;
}
void NTT(int *A, int type)
{
    for(int i = 0; i < limit; i++) if(i < r[i]) swap(A[i], A[r[i]]);
    for(int mid = 1; mid < limit; mid *= 2)
    {
        int Wn = qpow((type == 1 ? G : Gi), (P - 1) / (mid * 2));
        for(int j = 0; j < limit; j += (mid * 2))
        {
            int w = 1;
            for(int k = 0; k < mid; k++, w = (w * Wn) % P)
            {
                int x = A[j + k], y = w * A[j + k + mid] % P;
                A[j + k] = (x + y) % P; A[j + k + mid] = (x - y + P) % P;
            }
        }
    }
}
void calc(int t)
{
    for(int i = 0; i < limit; i++) b[i] = num[i];
    b[0] += t; NTT(a, 1); NTT(b, 1);
    for(int i = 0; i < limit; i++) a[i] = a[i] * b[i] % P;
    NTT(a, -1);
    for(int i = 0; i < limit; i++) a[i] = a[i] * Inv % P;
    for(int i = 0; i < limit; i++)
        a[i + 1] = (a[i + 1] + a[i] / 10) % P, a[i] %= 10;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    string s; cin >> s; int n = s.size() - 1;
    for(int i = 0; i <= n; i++) num[i] = (s[n - i] - '0');
    for(; limit <= 5 * (n + 1); l++, limit *= 2);
    for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    Inv = qpow(limit, P - 2);

    for(int i = 0; i < limit; i++) a[i] = num[i];
    a[0] += 1; calc(2); calc(3); calc(4);
    for(int i = limit - 1; i; i--) a[i - 1] += (a[i] % 24) * 10, a[i] /= 24;
    a[0] /= 24;

    int o = limit - 1; while(!a[o]) --o;
    for(int i = o; ~i; i--) cout << a[i];
    return 0;
}