LightOJ 1070 Algebraic Problem

题目在这里>_<

题意

给出$a+b$和$ab$的值，求$a^n+b^n$.
答案对$2^{64}$取模。

思路

先说说这个模数，这个模数很特殊，我们直接开unsigned long long让其自然溢出即可。
易得：$$(a^n+b^n)(a+b)=(a^{n+1}+b^{n+1}+ab(a^{n-1}+b^{n-1}))$$
令$A=a+b,B=ab,F(n)=a^n+b^n$，有
$$
\begin{bmatrix}
A & -B \\
1 & 0
\end{bmatrix}

\begin{bmatrix}
F(n) \\
A
\end{bmatrix}

=

\begin{bmatrix}
F(n+1) \\
A
\end{bmatrix}
$$

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <set>
//#define test
using namespace std;
const int Nmax=15;
typedef unsigned long long ll;
const ll mod=1LLu<<63;
struct Matrix
{
    int n,m;
    ll map[Nmax][Nmax];
    Matrix(int x,int y)
    {
        n=x;m=y;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                map[i][j]=0LLu;
    }
    Matrix operator * (const Matrix b)
    {
        Matrix c(n,b.m);
        if(m==b.n)
        {
            for(int i=1;i<=c.n;i++)
                for(int k=1;k<=m;k++)
                    for(int j=1;j<=c.m;j++)
                        c.map[i][j]=c.map[i][j]+map[i][k]*b.map[k][j];
            return c;
        }
        while(1)
        {

        }
        printf("error!!!!!!!!!!!!!!\n");   
        return c;
    }
    Matrix operator + (const Matrix b)
    {
        Matrix c(n,m);
        if(m==b.m && n==b.n)
        {
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    c.map[i][j]=map[i][j]+b.map[i][j];
            return c;
        }
        printf("error!!!!!!!!!!!!!!\n");   
        return c;
    }
    void show()
    {
        printf("n:%d m:%d\n",n,m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                printf("%4llu%c",map[i][j],j==m?'\n':' ');
    }
};
ll a,b,n;
ll work()
{
    Matrix base(2,2);
    base.map[1][1]=a,base.map[1][2]=-b;
    base.map[2][1]=1LLu;
    //base.show();
    Matrix ans(2,2);
    ans.map[1][1]=1LLu,ans.map[2][2]=1LLu;
    ll newa=a*a-2LLu*b;
    if(n==2)
        return newa;
    if(n==1)
        return a;
    if(n==0)
        return 2LLu;
    n-=2LLu;
    while(n)
    {
        if(n&1LLu)
            ans=ans*base;
        base=base*base;
        n>>=1;
    }
    Matrix now(2,1);
    now.map[1][1]=newa;
    now.map[2][1]=a;
    //ans.show();
    ans=ans*now;
    //now.show();
    return ans.map[1][1];
}
int main()
{
    #ifdef test
    #endif
    //freopen("b.in","r",stdin);
    int t=0;
    //printf("%llu\n",mod);
    //printf("%llu\n",mod*3LLu+1);
    scanf("%d",&t);
    t=0;
    while(~scanf("%llu%llu%llu",&a,&b,&n))
    {
        t++;
        if(!a && !b && !n)
            break;
        printf("Case %d: %llu\n",t,work());
    }
    return 0;
}