hdu 4990 Reading comprehension (构造矩阵，快速幂)

2017-09-30 · 2 min read · 构造矩阵快速幂

题目链接

题意：

给出了一段程序，程序实际算的是f[n] = (f[n-1] + n%2)%m的值，其中f[1]=1,给出n,m(1E9)，问f[n]

思路：

显然是矩阵快速幂，终点在于构造矩阵。

通过经验可得（这次真的是经验了。。。其实也挺容易的，要点大概在于先把需要的项列在一起，然后增加0或者多个，为了转移需要的辅助项。

根据当前列和下一列，手动构造转移矩阵）

转移矩阵M为

[2, 1,0]

[0,-1,1]

[0,0 ,1]

4A..都是一个原因。。矩阵乘法那里。。。就算你%了m..也是两个1E9在相乘。。。然后就炸了23333,改成LL即可。

/* ***********************************************
Author :111qqz
Created Time :2017年09月30日 星期六 19时08分59秒
File Name :4990.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;le
 6int n;
 7LL mod;
 8struct Mat
 9{
10    LL mat[8][8];
11    void clear()
12    {
13    ms(mat,0);
14    }
15}M,M1;

 1Mat operator * (Mat a,Mat b)
 2{
 3    Mat c;
 4    c.clear();
 5    for ( int i = 0 ; i < 3 ; i++)
 6    for ( int j  = 0 ; j < 3 ; j++)
 7        for ( int k = 0 ; k < 3 ; k++)
 8        c.mat[i][j] = (c.mat[i][j] + a.mat[i][k]%mod*b.mat[k][j]%mod)%mod;
 9    return c;
10}
11Mat operator ^ (Mat a,int b)
12{
13    Mat ret;
14    ret.clear();
15    for ( int i = 0 ; i < 3 ; i++) ret.mat[i][i] = 1;

 1    while (b>0)
 2    {
 3    if (b&1) ret = ret * a;
 4    a = a * a;
 5    b=b>>1;
 6    }
 7    return ret;
 8}
 9LL solve()
10{
11    M.clear();
12    M1.clear();
13    M.mat[0][0]=2;
14    M.mat[0][1]=1;
15    M.mat[1][1]=-1;
16    M.mat[1][2]=1;
17    M.mat[2][2]=1;

    M1.mat[0][0]=1;
    M1.mat[2][0]=1;

 1    Mat ans;
 2    ans.clear();
 3    ans = (M^(n-1))*M1;
 4    return ans.mat[0][0]%mod;
 5}
 6int main()
 7{
 8    #ifndef  ONLINE_JUDGE 
 9    //freopen("./in.txt","r",stdin);
10  #endif
11    while (~scanf("%d %lld",&n,&mod))
12    {
13        LL ans = solve();
14        ans = (ans % mod + mod)%mod;
15        printf("%lld\n",ans);
16    }

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}