題干：

Read the program below carefully then answer the question.?
#pragma comment(linker, "/STACK:1024000000,1024000000")?
#include <cstdio>?
#include<iostream>?
#include <cstring>?
#include <cmath>?
#include <algorithm>?
#include<vector>?

const int MAX=100000*2;?
const int INF=1e9;?

int main()?
{?
??int n,m,ans,i;?
??while(scanf("%d%d",&n,&m)!=EOF)?
??{?
????ans=0;?
????for(i=1;i<=n;i++)?
????{?
??????if(i&1)ans=(ans*2+1)%m;?
??????else ans=ans*2%m;?
????}?
????printf("%d\n",ans);?
??}?
??return 0;?
}

Input

Multi test cases，each line will contain two integers n and m. Process to end of file.?
[Technical Specification]?
1<=n, m <= 1000000000

Output

For each case，output an integer，represents the output of above program.

Sample Input

1 10 3 100

Sample Output

1 5

解題報(bào)告：

? ? ? 根據(jù)題干找規(guī)律，發(fā)現(xiàn)f(n) = f(n-1) + 2 * f(n-2) +1

AC代碼：

#pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include<iostream> #include <cstring> #include <cmath> #include <algorithm> #define ll long long struct Matrix {ll arr[4][4]; }unit,trans; ll n,m,ans; Matrix mul( Matrix a,Matrix b,ll mod) {Matrix c;for(int i = 1; i<=3; i++) {for(int j = 1; j<=3; j++) {c.arr[i][j] = 0; for(int k = 1; k<=3; k++) { // if(a.arr[i][k] && b.arr[k][j])c.arr[i][j] = (c.arr[i][j] + a.arr[i][k]*b.arr[k][j])%mod;}}}return c; } Matrix q_pow(Matrix a, ll k,ll mod) {Matrix ans;ans = unit;while(k) {if(k&1) {ans=mul(ans,a,m);}k>>=1;a=mul(a,a,m);}return ans; } void init() {memset(unit.arr,0,sizeof(unit.arr) );for(int i = 1; i<=3; i++) {unit.arr[i][i] = 1;trans.arr[i][1] = trans.arr[i][2] = trans.arr[i][3] = 0;}trans.arr[1][1]=trans.arr[1][3] =trans.arr[2][1]=trans.arr[3][3] = 1;trans.arr[1][2] = 2; } int main() { Matrix ans;ll sum=0;while(scanf("%lld%lld",&n,&m)!=EOF) {sum = 0;init();if(n==1) {printf("%lld\n",1%m);continue; }else if(n == 2) {printf("%lld\n",2%m);continue;}ans = q_pow(trans,n-2,m);sum = ans.arr[1][1]*2 + ans.arr[1][2]*1 + ans.arr[1][3];printf("%lld\n",sum%m);}return 0; }

總結(jié)：

? ? ? 這題坑很多啊，總是巧妙的跳了進(jìn)去。

? ? ? 1.全局變量ll的n和m，結(jié)果輸入用%d這個(gè)題的Mul函數(shù) 不是i<=n了！而是i<=3即可，i<=n就錯(cuò)了！ ?此題和HDU - 5015不一樣，不是矩陣是個(gè)不確定的矩陣！所以這里是小于等于3！！即

? ? ? 2.輸出的時(shí)候n=1和n=2需要特判一下，因?yàn)槟銈鲄⑹莕-2。即：這種地方一定要小心！你的函數(shù)是有使用條件的，這一點(diǎn)不僅適用于矩陣快速冪，還有很多其他的地方。

? ? ?3.輸出n==2的時(shí)候，別忘了也需要取模！！

? ? 4.最后的輸出 也需要取模！

總結(jié)

以上是生活随笔為你收集整理的【HDU - 4990】 Reading comprehension （构造+矩阵快速幂）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。