洛谷2012 拯救世界2

$$ \text{考虑对于每一种基因搞出来一个指数生成函，最后把他们乘起来。} \\ \text{注意到}\frac{\sin \left( ix \right)}{i}=\frac{\sinh \left( x \right)}{i}=\sum_{i\ge 0}{\frac{x^{2i+1}}{\left( 2i+1 \right) !}},\cos \left( ix \right) =\cosh \left( x \right) =\sum_{i\ge 0}{\frac{x^{2i}}{\left( 2i \right) !}} \\ \text{所以基因序列的生成函数为}F\left( x \right) =\left( \frac{\sinh \left( x \right)}{i}\cosh \left( x \right) e^x \right) ^4=\sinh \left( x \right) ^4\cosh \left( x \right) ^4e^{4x} \\ \text{大力麦克劳林展开发现} \\ F\left( x \right) =\frac{24}{\text{4!}}x^4+\frac{480}{\text{5!}}x^5+\frac{107520x^6}{\text{6!}}+\frac{1419264x^7}{\text{7!}}+\frac{18063360x^8}{\text{8!}}+\frac{225116160x^9}{\text{9!}}+…. \\ \text{所以答案即为}F^{\left( n \right)}\left( 0 \right) ,\text{同时注意到，对于}n<\text{4,答案为}0. \\ \text{经过}sympy\text{打表发现，答案极有可能是一个线性递推式，故写程序验证，发现} \\ f\left( n \right) =20f\left( n-1 \right) -80f\left( n-2 \right) -320f\left( n-3 \right) +1536f\left( n-4 \right) ,\text{同时} \\ f\left( 4 \right) =\text{24,}f\left( 5 \right) =\text{480,}f\left( 6 \right) =\text{7680,}f\left( 7 \right) =\text{107520，对于}k\le \text{3,}f\left( k \right) =0 \\ \text{然后直接矩乘即可通过本题}\left( \text{然而我一开始读入写挂导致在结尾没有回车或者空格的点}TLE \right) \\ \text{如果追求更高的速度，可以算一下这个递推的特征根，}x^4=20x^3-80x^2-320x+\text{1536,解得} \\ x=\left\{ -\text{4,4,8,}12 \right\} \\ \text{之后大力解方程求出来系数，故} \\ f\left( n-4 \right) =\left( -4 \right) ^n+6\times 4^n-64\times 8^n+81\times 12^n \\ \text{直接整数快速幂即可。} \\ $$

from sympy import *
x = symbols("x")
f = ((sinh(x)*cosh(x)*exp(x))**4).diff().diff().diff().diff()
coefs = []
for i in range(20):
    coefs.append(f.subs([(x, 0)]))
    f = f.diff()
print(coefs)

eqs = []
xs = list([symbols("x%d" % i) for i in range(8)])
A = 4
for i in range(A+4):
    a = 0
    for j in range(i, i+A):
        a += xs[j-i]*coefs[j]
    eqs.append(Eq(a, coefs[i+A]))
print(eqs)
print(solve(eqs))

#pragma GCC target("avx2,sse")
#include <assert.h>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
using int_t = unsigned long long int;
using std::cin;
using std::cout;
using std::endl;

const int mod = 1e9;
const int phi = 400000000;
template <class T>
void read(T& x) {
    x = 0;
    char chr = getchar();
    assert(chr != '-');
    int counter = 0;
    while (isdigit(chr) == false) {
        int curr = getchar();
        if (curr == -1) return;
        chr = curr;
        counter++;
        assert(counter <= 10);
    }
    while (isdigit(chr)) {
        x = x * 10 + (chr - '0');
        chr = getchar();
    }
}
template <class T>
void write(T x) {
    assert(x >= 0);
    if (x > 9) write(x / 10);
    putchar('0' + x % 10);
}
int main() {
    int counter = 0;
    while (true) {
        int_t x;
        read(x);
        if (x == 0) break;
        counter += 1;
        assert(counter <= 200000);
        if (x > phi) x = x % phi + phi;
        if (x < 4) {
            write(0);
            putchar('\n');
            continue;
        }
        x -= 4;
        int t2 = 1;
        int t3 = 1;
        int b3 = 3, b2 = 2;
        int index = x;
        while (index) {
            t2 = (int_t)t2 * ((index & 1) ? b2 : 1) % mod;
            t3 = (int_t)t3 * ((index & 1) ? b3 : 1) % mod;
            b3 = (int_t)b3 * b3 % mod;
            b2 = (int_t)b2 * b2 % mod;
            index >>= 1;
        }
        int t4 = (int_t)t2 * t2 % mod;
        int result = ((int_t)((x & 1) ? (mod - 1) : 1) + (int_t)81 * t3 + 6 -
                      (int_t)64 * t2 % mod + mod) %
                     mod * t4 % mod;
        write(result);
        putchar('\n');
    }
    return 0;
}