题解 P2012 【拯救世界2】
officeyutong
2019-02-24 15:40:38
使用Python3+Sympy实现的求递推系数的代码:
```python
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))
```
使用矩阵乘法通过本题的代码(由于我一开始没有注意到我读入函数写挂了故用了大量卡常手段):
```cpp
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#pra\
gma GCC optimi\
ze("Ofast")
#include <assert.h>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using int_t = unsigned long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t mod = 1e9;
struct Matrix {
int data[4][4];
int n, m;
Matrix() {
n = m = 0;
// memset(data, 0, sizeof(data));
}
Matrix(int n, int m) {
this->n = n;
this->m = m;
// memset(data, 0, sizeof(data));
#ifdef DEBUG
cout << "n=" << n << ",m=" << m << endl;
#endif
}
__attribute__((hot)) Matrix operator*(const Matrix& mat) {
Matrix result(n, mat.m);
for (short i = 0; i < n; i++) {
for (short j = 0; j < mat.m; j++) {
int_t sum = 0;
for (short k = 0; k < m; k++) {
sum += (int_t)data[i][k] * mat.data[k][j];
}
result.data[i][j] = sum % mod;
}
}
return result;
}
Matrix operator^(const Matrix& mat) {
Matrix result(n, mat.m);
result.data[0][0] = ((int_t)data[0][0] * mat.data[0][0] +
(int_t)data[0][1] * mat.data[1][0] +
(int_t)data[0][2] * mat.data[2][0] +
(int_t)data[0][3] * mat.data[3][0]) %
mod;
result.data[0][1] = ((int_t)data[0][0] * mat.data[0][1] +
(int_t)data[0][1] * mat.data[1][1] +
(int_t)data[0][2] * mat.data[2][1] +
(int_t)data[0][3] * mat.data[3][1]) %
mod;
result.data[0][2] = ((int_t)data[0][0] * mat.data[0][2] +
(int_t)data[0][1] * mat.data[1][2] +
(int_t)data[0][2] * mat.data[2][2] +
(int_t)data[0][3] * mat.data[3][2]) %
mod;
result.data[0][3] = ((int_t)data[0][0] * mat.data[0][3] +
(int_t)data[0][1] * mat.data[1][3] +
(int_t)data[0][2] * mat.data[2][3] +
(int_t)data[0][3] * mat.data[3][3]) %
mod;
return result;
}
int* operator[](int r) { return data[r]; }
};
template <class T>
void write(T x) {
if (x > 9) write(x / 10);
putchar('0' + x % 10);
}
Matrix base(1, 4), trans(4, 4);
Matrix pows[128];
int main() {
base[0][0] = 24;
base[0][1] = 480;
base[0][2] = 7680;
base[0][3] = 107520;
trans[1][0] = 1;
trans[2][1] = 1;
trans[3][2] = 1;
trans[0][3] = 1536;
trans[1][3] = mod - 320;
trans[2][3] = mod - 80;
trans[3][3] = 20;
pows[0] = trans;
for (int i = 1; i < 128; i++) {
pows[i] = pows[i - 1] * pows[i - 1];
}
int counter = 0;
while (true) {
int_t x;
cin>>x;
if (x == 0) break;
counter++;
if (counter > 200000) break;
if (x < 4) {
cout << 0 << endl;
continue;
}
x -= 4;
assert(x >= 0);
Matrix result = base;
int bit = 0;
while (x) {
if (x & 1) result = result ^ pows[bit];
bit++;
x >>= 1;
}
write(result.data[0][0]);
putchar('\n');
}
return 0;
}
```
使用特征方程通过本题的代码:
```cpp
#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;
}
```