danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

26244

[洛谷 P1962]斐波那契数列

2016年9月01日 13:18 | Comments(0) | Category:题解 | Tags:

线性代数的很多知识用一句欠揍的话形容就是:只可意会,不可言传。

友矩阵就是一个。友矩阵是一种应用于求递归数列的一种矩阵,作用是将一个旧的递归数列向量变成一个新的递归数列向量。友矩阵长相比较美(qi)观(pa),可以自行问度娘。

关于递归数列[tex]F[/tex],如果假设要用到的从前的信息可以组织为一个列向量[tex]F_{n-1}[/tex],若已知其友矩阵为[tex]A[/tex],则有下公式(这个推导其实并不难,如果你用解线性方程组的思维来看的话):

[tex]F_n=A\mul F_{n-1}[/tex]

可知(假设要用到的从前的信息为[tex]d[/tex]):

[tex]F_n=A^{n-d}*F_d[/tex]

然后我们发现求[tex]A^{n-d}[/tex]可以使用快速幂,这就简单了^_^

不过有个不错的小技巧:快速幂结果矩阵的初始值处理让人很头疼,不过可以直接使用单位矩阵,这样就相当于通常计算中的1辣~

代码:

#include <iostream>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
typedef ull Matrix[2][2];
const ull MOD=1000000007;
#define REP(i,n) for(i=0;i<(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
#define CP_ARR(from,to) memcpy(to,from,sizeof(from))

inline void MatrixMul(Matrix A,Matrix B,int m,int n,int p,Matrix& res){
    Matrix C;
    register int i,j,k;
    CL_ARR(C,0);
    REP(i,m){
        REP(j,p){
            REP(k,n){
                C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%MOD)%MOD;
            }
        }
    }
    CP_ARR(C,res);
}
void MatrixPow(Matrix A,ull x,Matrix& res){
    Matrix a,temp;
    register int i;
    bool used=false;
    memcpy(a,A,sizeof(a));
    CL_ARR(temp,0);
    temp[0][0]=1;
    temp[1][1]=1;
    while(x){
        if(1&x){
            MatrixMul(temp,a,2,2,2,temp);
        }
        x>>=1;
        MatrixMul(a,a,2,2,2,a);
    }
    CP_ARR(temp,res);
}
Matrix Q={{0,1},{1,1}};
Matrix Fib={{1,0},{1,0}};
int main(){
    ull n;
    ios::sync_with_stdio(NULL);
    cin.tie(0);
    cin>>n;
    if(n<=2){
        cout<<1<<endl;
    }else{
        MatrixPow(Q,n-2,Q);
        MatrixMul(Q,Fib,2,2,1,Fib);
        cout<<Fib[1][0]<<endl;
    }
    return 0;
}

[BZOJ 1002]轮状病毒

2016年1月24日 12:53 | Comments(0) | Category:题解 | Tags:

根据Matrix-Tree定理,这题可以求出基尔霍夫矩阵,然后当成行列式求值即可

这样做并没有什么错,大概也能AC,但是时间复杂度是立方级的,并且写起来并不简单(要用到高斯消元什么的,更何况此题还要用高精度)

或许DP也可以?

不过有一个简单的递推式:d[n]=d[n-1]*3-d[n-2]+2

证明比较麻烦(绝大多数人是找规律出来的),可以到这找:http://vfleaking.blog.163.com/blog/static/17480763420119685112649

这题要用高精也太烦人了,我就用了Python写(Python语法真特么烦人啊)

Q:真要考试你交Python啊?

A:我用Python打出来表然后交表啊。

代码: