P2012 solution

· · 题解

想必来做这题的人都做过 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) 可以稍微预处理一下，每组数据时间复杂度为 $\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));
    }
}