Recursive sequence （矩阵快速幂）2016ACM/ICPC亚洲区沈阳站

题目

Farmer John likes to play mathematics games with his $\mathrm{N cows.\; Recently,\; they\; are\; attracted\; by\; recursive\; sequences.\; In\; each\; turn,\; the\; cows\; would\; stand\; in\; a\; line,\; while\; John\; writes\; two\; positive\; numbers a and b on\; a\; blackboard.\; And\; then,\; the\; cows\; would\; say\; their\; identity\; number\; one\; by\; one.\; The\; first\; cow\; says\; the\; first\; number a and\; the\; second\; says\; the\; second\; number bb.\; After\; that,\; the ii-th\; cow\; says\; the\; sum\; of\; twice\; the (i-2)-th\; number,\; the (i-1)-th\; number,\; and i^4.\; Now,\; you\; need\; to\; write\; a\; program\; to\; calculate\; the\; number\; of\; the N-th\; cow\; in\; order\; to\; check\; if\; John’s\; cows\; can\; make\; it\; right.}$

Input

The first line of input contains an integer $\mathrm{t,\; the\; number\; of\; test\; cases. tt test\; cases\; follow.}$

Each case contains only one line with three numbers $\mathrm{N, aa and bb where N,a,b<2^31 as\; described\; above.}$

Output

For each test case, output the number of the $\mathrm{NN-th\; cow.\; This\; number\; might\; be\; very\; large,\; so\; you\; need\; to\; output\; it\; modulo 2147493647.}$

In the first case, the third number is $85 = 21+2+3^4$.Inthesecondcase,thethirdnumberis.Inthesecondcase,thethirdnumberis93\; =\; 2$1+1*10+3^4$\mathrm{andthefourthnumberisandthefourthnumberis369\; =\; 2\; *\; 10\; +\; 93\; +\; 4^4\$.}$

$\mathrm{题意}$

$\mathrm{题目给出这样一个递推公式：}$

$f$$\mathrm{(n)=f(n-2)*2+f(n-1)+n^\; 4}$

$\mathrm{f(1)=a,}$

$\mathrm{f(2)=b;}$

给出n,a,b求f(n)%2147493647；

根据递推公式容易得出一个O（N)的暴力算法。但这题的数据范围为N,a,b<2^31 ，直接暴力肯定超时，要用O（1），O（lngn）或者是O（n^(1/2)）的算法才有可能ac

观察这种递推公式，发现我们可以使用矩阵快速幂来计算，矩阵快速幂的复杂度是O（m^3 *lngn）m是矩阵的大小，复杂度很小可以一试。

矩阵快速幂是定义一个状态矩阵和一个转移矩阵，前一个状态矩阵乘转移矩阵可得到后一个状态矩阵。

这题和普通的矩阵快速幂有点区别,这题的递推函数在混合了一个变量n^4。

所以我们这题首先要考虑的就是，如何从n^4推出(n+1)^4，我们发现通过二项式定理可以得出，(n+1)^4=n^4+4n^3+6n^2+4n+1

这样就有f(n+1)=2*f(n-1)+f(n)+n^4+4n^3+6n^2+4n+1

不妨设状态矩阵F(n-1)=[f(n-1),f(n),n^4,4n^3,6n^2,4n,1]

若F(n)=F(N-1)*A 即[f(n),f(n+1),(n+1)^4,4(n+1)^3,6(n+1)^2,4(n+1),1]=[f(n-1),f(n),n^4,4n^3,6n^2,4n,1]*A

计算得A=

{0,2,0,0,0,0,0}
{1,1,0,0,0,0,0}
{0,1,1,0,0,0,0}
{0,1,1,1,0,0,0}
{0,1,1,2,1,0,0}
{0,1,1,3,3,1,0}
{0,1,1,4,6,4,1}

 

AC代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
const ll mod=2147493647;
ll n;

void mul(ll f[7],ll a[7][7]){
    ll c[7];
    memset(c,0,sizeof(c));
    for(ll j=0;j<7;j++)
        for(ll k=0;k<7;k++)
            c[j]=(c[j]+(ll)f[k]*a[k][j])%mod;
    memcpy(f,c,sizeof(c));
}

void mulself(ll a[7][7]){
    ll c[7][7];
    memset(c,0,sizeof(c));
    for(ll i=0;i<7;i++)
        for(ll j=0;j<7;j++)
            for(ll k=0;k<7;k++)
                c[i][j]=(c[i][j]+(ll)a[i][k]*a[k][j])%mod;
    memcpy(a,c,sizeof(c));

}


int main(){
    ll t,a,b;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld%lld",&n,&a,&b);
        ll f[]={a,b,16,32,24,8,1};
        ll a[][7]={
            {0,2,0,0,0,0,0},
            {1,1,0,0,0,0,0},
            {0,1,1,0,0,0,0},
            {0,1,1,1,0,0,0},
            {0,1,1,2,1,0,0},
            {0,1,1,3,3,1,0},
            {0,1,1,4,6,4,1},
        };
        n--;
        for(;n;n>>=1){
            if(n&1)mul(f,a);
            mulself(a);
        }
        printf("%lld
",f[0]);

    }
    
}