本文共 5092 字，大约阅读时间需要 16 分钟。

题目大意

给出一个如下的递推式，给出前两项求第$n$项：

$f(n)=f(n-1)+2f(n-2)+n^4$

解题思路

对于$n^4$，实际上和$f(n)$并不是递推关系，一开始想的是将$n^4$和前面部分拆开来求，但是这样是错误的，不能拆开，因此考虑以下思路：

$n^4=[(n-1)+1{]}^4=C_4^0(n-1{)}^4+C_4^1(n-1{)}^3+C_4^2(n-1{)}^2+C_4^1(n-1)+1$

那么有$f(n)=f(n-1)+2f(n-2)+C_4^0(n-1{)}^4+C_4^1(n-1{)}^3+C_4^2(n-1{)}^2+C_4^1(n-1)+1$

对于这个东西，我们首先设$X_{n-1}=\left[\begin{array}{c}f(n-1)\\ f(n-2)\\ (n-1{)}^4\\ (n-1{)}^3\\ (n-1{)}^2\\ (n-1{)}^1\\ 1\end{array}\right]$

那么不难得出$X_n=\left[\begin{array}{c}f(n)\\ f(n-1)\\ n^4\\ n^3\\ n^2\\ n^1\\ 1\end{array}\right]$

考虑构造出一个$7\times 7$的方阵$m$使得$X_n=m\ast X_{n-1}$，我们可以首先假设所有项都为未知数，然后根据矩阵乘法的规律，可以求出每一项，最后可以得到：

$m=\left[\begin{array}{ccccccc}1& 2& 1& 4& 6& 4& 1\\ 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 4& 6& 4& 1\\ 0& 0& 0& 1& 3& 3& 1\\ 0& 0& 0& 0& 1& 2& 1\\ 0& 0& 0& 0& 0& 1& 1\\ 0& 0& 0& 0& 0& 0& 1\end{array}\right]$

那么最后的递推矩阵式为：

$\left[\begin{array}{c}f(n)\\ f(n-1)\\ n^4\\ n^3\\ n^2\\ n^1\\ 1\end{array}\right]={\left[\begin{array}{ccccccc}1& 2& 1& 4& 6& 4& 1\\ 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 4& 6& 4& 1\\ 0& 0& 0& 1& 3& 3& 1\\ 0& 0& 0& 0& 1& 2& 1\\ 0& 0& 0& 0& 0& 1& 1\\ 0& 0& 0& 0& 0& 0& 1\end{array}\right]}^{n-2}\left[\begin{array}{c}f(2)\\ f(1)\\ 2^4\\ 2^3\\ 2^2\\ 2^1\\ 1\end{array}\right]$

代码

//// Created by Happig on 2020/10/25//#include <bits/stdc++.h>#include <unordered_map>#include <unordered_set>using namespace std;#define fi first#define se second#define pb push_back#define ins insert#define Vector Point#define ENDL "\n"#define lowbit(x) (x&(-x))#define mkp(x, y) make_pair(x,y)#define mem(a, x) memset(a,x,sizeof a);typedef long long ll;typedef long double ld;typedef unsigned long long ull;typedef pair<int, int> pii;typedef pair<ll, ll> pll;typedef pair<double, double> pdd;const double eps = 1e-8;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double dinf = 1e300;const ll INF = 1e18;const ll Mod = 2147493647;const int maxn = 2e5 + 10;const int arr1[10][10] = {   {   1, 2, 1, 4, 6, 4, 1},                          {   1, 0, 0, 0, 0, 0, 0},                          {   0, 0, 1, 4, 6, 4, 1},                          {   0, 0, 0, 1, 3, 3, 1},                          {   0, 0, 0, 0, 1, 2, 1},                          {   0, 0, 0, 0, 0, 1, 1},                          {   0, 0, 0, 0, 0, 0, 1}};int arr2[] = {   0, 0, (1 << 4), (1 << 3), (1 << 2), (1 << 1), 1};struct Matrix {       ll matrix[10][10];    int n, m;    Matrix() {   }    Matrix(int x, int y) {           n = x, m = y;        memset(matrix, 0, sizeof(matrix));    }};Matrix mul(Matrix a, Matrix b) {       Matrix ans(a.n, b.m);    for (int i = 1; i <= ans.n; i++) {           for (int j = 1; j <= ans.m; j++) {               for (int k = 1; k <= a.m; k++) {                   ans.matrix[i][j] += a.matrix[i][k] * b.matrix[k][j] % Mod;                ans.matrix[i][j] %= Mod;            }        }    }    return ans;}Matrix qkp(Matrix mx, ll n) {       Matrix ans(mx.n, mx.m);    for (int i = 1; i <= mx.n; i++) ans.matrix[i][i] = 1;    while (n) {           if (n & 1) ans = mul(ans, mx);        mx = mul(mx, mx);        n >>= 1;    }    return ans;}ll solve(ll n) {       if (n == 1) return arr2[1];    if (n == 2) return arr2[0];    Matrix mx(7, 7);    for (int i = 1; i <= 7; i++) {           for (int j = 1; j <= 7; j++) {               mx.matrix[i][j] = arr1[i - 1][j - 1];        }    }    Matrix dw(7, 1);    for (int i = 1; i <= 7; i++) {           dw.matrix[i][1] = arr2[i - 1];    }    Matrix ans = mul(qkp(mx, n - 2), dw);    return ans.matrix[1][1];}int main() {       //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n, T;    cin >> T;    while (T--) {           cin >> n >> arr2[1] >> arr2[0];        cout << solve(n) << endl;    }    return 0;}