洛谷P2012 拯救世界2 题解

题目链接：P2012 拯救世界2

题意：

经过 12 年的韬光养晦，世界末日再次来临（众人：什么鬼逻辑……）。

这次，小a 和 uim 已经做好了一切准备，顺利召唤出了 kkksc03 大神和 lzn 大神。然而，kkksc03 和 lzn 告诉他们，这次世界末日太过强大，他们已无法挽回，只有创世神 JOHNKRAM 能拯救这个世界。

然而，创世神 JOHNKRAM 是无法召唤的，除非把整个宇宙按照 $E=mc^2$ 全部转化成能量。因为根据 C_SUNSHINE 大神随手推算出的召唤定律，至少需要被召唤者百万亿分之一的能量才能召唤（众人：什么鬼定律……）。

当然，还有一种方法，那就是找出创世神 JOHNKRAM 的基因序列。普通人基因序列由 A、C、G、T 构成，创世神 JOHNKRAM 不是普通人（是个胖纸），基因序列也不一样。除了这四种普通的，还有乾、兑、离、震、巽、坎、艮、坤八种特殊基因。其中乾、坎、艮、震属阳，只能出现奇数次；坤、兑、离、巽属阴，只能出现偶数次。

现在只知道创世神 JOHNKRAM 的基因序列共有 $n$ 位，其他一概不知。小a 和 uim 想知道他们最多要试多少次，才能召唤出创世神 JOHNKRAM 。这个数字有可能很大，所以输出答案模 $10^9$ 即可（C_SUNSHINE 的忠告：远离八卦，远离肥胖）。

输入格式：

输入由多组数据组成，每组数据一行，输入一个数 $n$，输入以 $0$ 结束。

输出格式：

对于每组数据，输出一行一个整数，表示答案对 $10^9$ 取模的结果。

数据范围：

对于 $100\%$ 的数据：$1\le n < 2^{63}$，数据不超过 $2\times 10^5$ 组。

首先假设你已经看过了洛谷P2000 拯救世界题解，或者做了那道题。

之所以那道题可以用 OGF 算，是因为它是方案都是无序的，而在本题中方案是有序的。

于是我们就需要用到 EGF 了，也就是指数生成函数。

对于数列 $\{a_i\}$ ，其指数生成函数 $A_i$ 定义为

$A(x) = \sum_{n \ge 0} \frac{a_i}{i!} x^n$

考虑列出题目中的三种基因所对应的 EGF ，方法的话和 OGF 是差不多的。

$f(x)=\sum_{i=0}^{\infty} \frac{x^i}{i !}=\mathrm{e}^x \\ g(x)=\sum_{i=0}^{\infty} \frac{x^{2 i}}{(2 i) !}=\frac{1}{2}\left(\mathrm{e}^x+\mathrm{e}^{-x}\right) \\ h(x)=\sum_{i=0}^{\infty} \frac{x^{2 i+1}}{(2 i+1) !}=\frac{1}{2}\left(\mathrm{e}^x-\mathrm{e}^{-x}\right)$

然后把他们乘起来

$\begin{aligned} A(x)&=(f(x) g(x) h(x))^4 \\[6pt]&=\left(\frac{1}{4} \mathrm{e}^x\left(\mathrm{e}^{2 x}-\mathrm{e}^{-2 x}\right)\right)^4 \\[6pt]&=\left(\frac{1}{4}\left(\mathrm{e}^{3 x}-\mathrm{e}^{-x}\right)\right)^4 \\[6pt]&=\frac{1}{256}\left(\mathrm{e}^{12 x}-4 \mathrm{e}^{8 x}+6 \mathrm{e}^{4 x}-4+\mathrm{e}^{-4 x}\right) \end{aligned}$

答案就是第 $n$ 项系数乘上 $n!$

$\begin{aligned} n !\left[x^n\right] A(x) &= \frac{n !}{256}\left(\frac{12^n}{n !}-\frac{4 \times 8^n}{n !}+\frac{6 \times 4^n}{n !}+\frac{(-4)^n}{n !}\right) \\[6pt]&=\frac{1}{256}\left(12^n-4 \times 8^n+6 \times 4^n+(-4)^n\right) \end{aligned}$

但是注意，本题的模数是 $10^9$ ，而 $256$ 在模 $10^9$ 下没有逆元。

$81 \times 12^{n-4}-8^{n-2}+6 \times 4^{n-4}+(-4)^{n-4}$

因此我们要以上式作为答案，并对 $n$ 较小时的情况暴力计算（打表即可）。

另外，这题非常卡常，对于 $n \ge \varphi(10^9) \Rightarrow n \ge 4\times 10^8$ 的情况也需要处理一下，并且最好用光速幂。

所谓光速幂，其实就是把固定底数 $a$ 的次幂按 $a^k\,(k \le 2^{15})$ 和 $a^{k+2^{15}}$ 分别预处理，然后 $\mathcal{O}(1)$ 查表。

时间复杂度 $\mathcal{O}(2^{15} + 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)(32768 + 4))

const int p = 1e9;
const int phi = 4e8;
const int ans[] = {0,0,0,0,24,480,7680,107520};

int n,pw1[N],pw2[N],pw3[N],pw4[N];
int qry(int n)
{
    int x = pw1[n & 32767] * pw2[n >> 15] % p, y = x * x % p;
    int res = (81 * pw3[n & 32767] % p * pw4[n >> 15] % p - 64 * x % p * y % p) % p;
    res = (res + 6 * y + p) % p;
    return (n & 1) ? (res < y ? res - y + p : res - y) : (res + y >= p ? res + y - p : res + y);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    pw1[0] = pw2[0] = pw3[0] = pw4[0] = 1;
    pw1[1] = 2;
    for(int i = 2; i < 32768; i++) pw1[i] = pw1[i - 1] * 2 % p;
    pw2[1] = pw1[32768 - 1] * 2 % p;
    for(int i = 2; i < 32768; i++) pw2[i] = pw2[i - 1] * pw2[1] % p;
    pw3[1] = 12;
    for(int i = 2; i < 32768; i++) pw3[i] = pw3[i - 1] * 12 % p;
    pw4[1] = pw3[32768 - 1] * 12 % p;
    for(int i = 2; i < 32768; i++) pw4[i] = pw4[i - 1] * pw4[1] % p;
    while(cin >> n && n)
    {
        int x = (n >= phi) ? (n % phi + phi) : n;
        cout << (x < 8 ? ans[x] : qry(x - 4)) << '\n';
    }
    return 0;
}