應用矩陣快速冪運算可以解決遞推問題。在實際應用中，有時候題目並沒有直接給出遞推式，需要認真分析問題，找出遞推式，然後再利用矩陣快速冪運算加快問題的求解。 【例1】程式閱讀理解。 有如下的C語言程式： #include <stdio.h>int main(){ int n,m,f,i; while(s ...
應用矩陣快速冪運算可以解決遞推問題。在實際應用中，有時候題目並沒有直接給出遞推式，需要認真分析問題，找出遞推式，然後再利用矩陣快速冪運算加快問題的求解。
【例1】程式閱讀理解。
有如下的C語言程式：
#include <stdio.h>
int main()
{
int n,m,f,i;
while(scanf("%d%d",&n,&m)!=EOF)
{
f=0;
for(i=1;i<=n;i++)
{
if (i&1)f=(f*2+1)%m;
else f=f*2%m;
}
printf("%d\n",f);
}
return 0;
}
閱讀上面的程式，根據輸入的n和m，寫出程式運行的結果。例如，輸入 3 10，輸出應為5。
但由於給定輸入的n和m的數據範圍為1<=n, m <= 1000000000，且測試集中數據量較大，因此如果直接將給定的程式提交會超時的。請你編寫一個程式，能根據輸入的n和m快速完成問題的求解，以實現給定程式的功能。
（1）編程思路。
給定程式段實際是通過迭代的方式求f(n)%m的值。先不考慮求餘，找到f(n)的求法。
分析給定程式知，f(0)=0， 當 n為奇數時，f(n)=2*f(n-1)+1；當n為偶數時，f(n)=2*f(n-1)。
下麵進一步分析，找到不考慮n的奇偶性的一個統一的遞推式。
當 n為奇數時，f(n)=2*f(n-1)+1，n-1一定為偶數，f(n-1)=2*f(n-2)。因此，
f(n)=f(n-1)+f(n-1)+1=2*f(n-2)+f(n-1)+1。
當 n為偶數時，f(n)=2*f(n-1)，n-1一定為奇數，f(n-1)=2*f(n-2)+1。因此，
f(n)=f(n-1)+f(n-1)=2*f(n-2)+f(n-1)+1。
由此，得到統一的遞推式： f(0)=0，f(1)=1， f(n)=2*f(n-2)+f(n-1)+1 (n>=3)。
確定了遞推式後，可以構造矩陣P，進行快速冪運算求解。
（2）源程式。
#include <stdio.h>
#include <string.h>
struct Matrix
{
__int64 mat[4][4]; // 存儲矩陣中各元素
};
Matrix matMul(Matrix a ,Matrix b,int n,int m)
{
Matrix c;
memset(c.mat,0,sizeof(c.mat));
int i,j,k;
for (k = 1; k<=n ; k++)
for (i=1 ;i<=n ; i++)
if (a.mat[i][k]!=0)
for (j = 1 ;j<=n ;j++)
c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % m;
return c;
}
Matrix quickMatPow(Matrix a ,int n,int b,int m) // n階矩陣a快速b次冪
{
Matrix c;
memset(c.mat ,0 ,sizeof(c.mat));
int i;
for (i = 1 ;i <= n ;i++)
c.mat[i][i] = 1;
while (b!=0)
{
if (b & 1)
c = matMul(c ,a ,n,m); // c=c*a;
a = matMul(a ,a ,n,m); // a=a*a
b /= 2;
}
return c;
}
int main()
{
int n,m;
__int64 ans;
Matrix p;
while(scanf("%d%d" ,&n,&m)!=EOF)
{
memset(p.mat,0,sizeof(p.mat));
p.mat[2][1]=2;
p.mat[1][2]=p.mat[2][2]=1;
p.mat[2][3]=p.mat[3][3]=1;
if (n<3)
printf("%d\n",n%m);
else
{
p = quickMatPow(p,3,n-2,m);
ans=p.mat[2][1]% m;
ans=(ans+p.mat[2][2]*2)% m;
ans=(ans+p.mat[2][3])% m;
printf("%I64d\n" ,ans);
}
}
return 0;
}
將此源程式提交給HDU 4990 “Reading comprehension”，可以Accepted。
【例2】將燈全熄滅。
有n個燈排成一行，初始時是全亮的，第一個燈可以按（按下之後改變狀態）。然後如果前k個燈全熄滅且第k+1個燈亮，則第k+2個燈可以按。問至少要多少步滅掉所有燈？
例如，n=2時，需要2歩。第1歩滅掉2號燈，第2歩滅掉1號燈。n=3時，需要5歩。第1歩滅掉1號燈，第2歩滅掉3號燈，第3歩點亮1號燈（註意1號燈不點亮，不能直接滅2號燈），第4歩滅掉2號燈，第5歩滅掉1號燈。
（1）編程思路。
設f[n]代表n個全亮的燈變成全熄滅所需的最少步數，也可以代表n個全熄滅的燈變成全點亮所需的最少步數。
1）要想滅掉最後一個燈，得先滅掉前n-2個燈（第n-1個燈留亮），需要步數 f[n-2]+1。
2）要想滅掉第n-1個燈，得先讓第n-2個燈變回亮，要第n-2個燈變回亮，得先讓第n-3個燈變回亮...即要把前n-2個燈都變回亮，需要步數 f[n-2]。
3）把前n-2個燈變回亮後，就剩下前n-1個燈都是亮的，即剩下的任務就是把n-1個燈滅掉，需要步數 f[n-1]。
綜上所述：f[n] = 2*f[n-2] + f[n-1] + 1。 （n>=3） f[1]=1，f[2]=2。
（2）源程式。
#include <stdio.h>
#include <string.h>
#define MOD 200907
struct Matrix
{
__int64 mat[4][4]; // 存儲矩陣中各元素
};
Matrix matMul(Matrix a ,Matrix b,int n)
{
Matrix c;
memset(c.mat,0,sizeof(c.mat));
int i,j,k;
for (k = 1; k<=n ; k++)
for (i=1 ;i<=n ; i++)
if (a.mat[i][k]!=0)
for (j = 1 ;j<=n ;j++)
c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD;
return c;
}
Matrix quickMatPow(Matrix a ,int n,int b) // n階矩陣a快速b次冪
{
Matrix c;
memset(c.mat ,0 ,sizeof(c.mat));
int i;
for (i = 1 ;i <= n ;i++)
c.mat[i][i] = 1;
while (b!=0)
{
if (b & 1)
c = matMul(c ,a ,n); // c=c*a;
a = matMul(a ,a ,n); // a=a*a
b /= 2;
}
return c;
}
int main()
{
int n;
__int64 ans;
Matrix p;
while(scanf("%d" ,&n) && n!=0)
{
memset(p.mat,0,sizeof(p.mat));
p.mat[1][2]=2;
p.mat[1][1]=p.mat[1][3]=1;
p.mat[2][1]=p.mat[3][3]=1;
if (n<3)
printf("%d\n",n%MOD);
else
{
p = quickMatPow(p,3,n-2);
ans=(p.mat[1][1]*2+p.mat[1][2]+p.mat[1][3])%MOD;
printf("%I64d\n" ,ans);
}
}
return 0;
}
將此源程式提交給HDU 2842 “Chinese Rings”，可以Accepted。
