M_sea

UVA10655 Contemplation! Algebra
UVaLuoguVjudge分析做这题的时候 SB 了,竟然没推出来 QAQ考虑设 $f_n=a^n+b^n$ 。...
扫描右侧二维码阅读全文
10
2019/09

UVA10655 Contemplation! Algebra

UVa

Luogu

Vjudge

分析

做这题的时候 SB 了,竟然没推出来 QAQ

考虑设 $f_n=a^n+b^n$ 。如果熟悉小学奥数的话可以得到

$$ \begin{aligned} a^n+b^n&=(a+b)(a^{n-1}+b^{n-1})-(ab^{n-1}+ba^{n-1})\\ &=(a+b)(a^{n-1}+b^{n-1})-ab(a^{n-2}+b^{n-2})\\ \end{aligned} $$

也就是说

$$ f_n=pf_{n-1}-qf_{n-2} $$

显然可以矩阵加速:

$$ \begin{bmatrix}f_{n-1}&f_{n-2}\end{bmatrix}\times\begin{bmatrix}p&1\\-q&0\end{bmatrix}=\begin{bmatrix}f_{n}&f_{n-1}\end{bmatrix} $$

边界为 $f_0=2,f_1=p$ 。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

int p,q,n;

struct Matrix {
    ll s[2][2];
    Matrix() { s[0][0]=s[0][1]=s[1][0]=s[1][1]=0; }
    ll* operator [](int i) { return s[i]; }
} A,B;
Matrix operator *(Matrix a,Matrix b) {
    Matrix c;
    for (re int i=0;i<2;++i)
        for (re int k=0;k<2;++k)
            for (re int j=0;j<2;++j)
                c[i][j]+=a[i][k]*b[k][j];
    return c;
}
inline Matrix qpow(Matrix a,int b) {
    Matrix c; c[0][0]=c[1][1]=1;
    for (;b;b>>=1,a=a*a) if (b&1) c=c*a;
    return c;
}

int main() {
    while (scanf("%d%d%d",&p,&q,&n)==3) {
        if (!n) { puts("2"); continue; }
        A[0][0]=p,A[0][1]=2;
        B[0][0]=p,B[0][1]=1,B[1][0]=-q,B[1][1]=0;
        printf("%lld\n",(A*qpow(B,n-1))[0][0]);
    }
    return 0;
}
最后修改:2019 年 09 月 10 日 09 : 31 PM

1 条评论

  1. Karry5307

    这不是小学奥数,这是初中MO

发表评论