hdu 4990 Reading comprehension (构造矩阵,快速幂)
题意:
给出了一段程序,程序实际算的是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}