自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 21:32:56，当前版本为作者最后更新于2019-08-12 13:58:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

想必来做这题的人都做过 P2000 拯救世界 吧。
在那题中，方案都是无序的，所以用普通生成函数解决。 而在这题中是有序的，这时就要使用指数型生成函数(EGF)。

有一个数列 $a$，其 EGF 就是：

$$\sum\limits_{i=0}^\infty \frac{x^i}{i!}a_i$$

那么我们根据题目中的三种基因，可以列出它们的 EGF：

$$f(x)=\sum\limits_{i=0}^\infty \frac{x^i}{i!}=\text e^x $$$$g(x)=\sum\limits_{i=0}^\infty \frac{x^{2i}}{(2i)!}=\frac12(\text e^x+ \text e^{-x}) $$$$h(x)=\sum\limits_{i=0}^\infty \frac{x^{2i+1}}{(2i+1)!}=\frac12(\text e^x-\text e^{-x}) $$

---

和 P2000 那题一样，答案的 EGF 就是把它们都乘起来

$$A(x)=(f(x)g(x)h(x))^4$$ $$=(\frac14e^x(\text e^{2x}-\text e^{-2x}))^4$$ $$=(\frac14(\text e^{3x}-\text e^{-x}))^4$$ $$=\frac{1}{256}(\text e^{12x}-4\text e^{8x}+6\text e^{4x}-4+\text e^{-4x}) $$

---

那么答案就是取其 $n$ 次项系数，不过要注意乘个 $n!$

$$\text{ans}=n![x^n]A(x)$$ $$=\frac{n!}{256}(\frac{12^n}{n!}-\frac{4\times8^n}{n!}+\frac{6\times4^n}{n!}+\frac{(-4)^n}{n!}) $$$$= \frac{1}{256}(12^n-4\times8^n+6\times4^n+(-4)^n) $$

这样就可以计算了，，

不过要注意的是 $256$ 在模 $10^9$ 下没有逆元，所以在 $n$ 较小的时候直接暴力，否则答案就是

$$81\times12^{n-4}-8^{n-2}+6\times4^{n-4}+(-4)^{n-4} $$

直接快速幂就能解决。

但是这题极度卡常，要用一个小小的优化。
根据扩展欧拉定理：

$$a^{b} \equiv \left\{\begin{aligned} a^{b\text{ mod }φ(m)+φ(m)}\space(b\geφ(m)) \\ a^b\space(b<φ(m))\end{aligned}\right.(\text{mod }m) $$

$φ(10^9)=4\times10^8$，所以只要 $n\ge4\times10^8$ 就对其取模再加上去就好了。

可以稍微预处理一下，每组数据时间复杂度为 $\Theta(1)$

Code:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define reg register
#define ll long long
#define p 1000000000
#define phi 400000000
using namespace std;

int table[8] = {0,0,0,0,24,480,7680,107520};
int pw1[32769],pw2[32769],pw3[32769],pw4[32769];

inline int solve(const int& n){
    reg int x = (ll)pw1[n&32767]*pw2[n>>15]%p,y = (ll)x*x%p;
    reg int res = (81ll*pw3[n&32767]%p*pw4[n>>15]%p-64ll*x%p*y)%p;
    res = (res+6ll*y+p)%p;
    return (n&1)?(res<y?res-y+p:res-y):(res+y>=p?res+y-p:res+y);
}

int main(){
    pw1[0] = pw2[0] = pw3[0] = pw4[0] = 1;
    pw1[1] = 2;
    for(reg int i=2;i<=32768;++i) pw1[i] = pw1[i-1]<500000000?(pw1[i-1]<<1):(pw1[i-1]<<1)-p;
    pw2[1] = pw1[32768];
    for(reg int i=2;i<=32768;++i) pw2[i] = (ll)pw2[i-1]*pw2[1]%p;
    pw3[1] = 12;
    for(reg int i=2;i<=32768;++i) pw3[i] = (ll)pw3[i-1]*12%p;
    pw4[1] = pw3[32768];
    for(reg int i=2;i<=32768;++i) pw4[i] = (ll)pw4[i-1]*pw4[1]%p;
    reg ll n;
    reg int x;
    while(cin>>n){
    	if(n==0) break;
        x = n>=phi?n%phi+phi:n;
        printf("%d\n",x<8?table[x]:solve(x-4));
    }
}