http://acm.pku.edu.cn/JudgeOnline/problem?id=3420好几个人都问我这道题,可是我自己也不会做,真是惭愧啊...太落后了..别人都飞机大炮了,我还在小米加步枪.... 太羞愧了 ..
不过还好,除了Felicia的程序以外(
http://www.cppblog.com/felicia/archive/2007/10/08/33740.html),我还读了两个牛人的程序.
一个是
Ricky_的
1
#include "stdio.h"
2
int matrix[4][4] = 
{ {0,0,0,-1},
3
{1,0,0,1},
4 {0,1,0,5},
5 {0,0,1,1}};
6int n, m;
7int tmp[4][4], quo[4][4], ans[4];
8
9void MatrixCopy( int to[][4], int from[][4] ){
10
int i, j;
11 for ( i = 0; i < 4; i++ ){
12 for ( j = 0; j < 4; j++ ){
13 to[ i ][ j ] = from[ i ][ j ];
14
}
15 }
16
}
17void MatrixMulti( int a[][4], int b[][4], int c[][4] ){
18 int i, j, k, t;
19 for ( i = 0; i < 4; i++ ){
20 for ( j = 0; j < 4; j++ ){
21 t = 0;
22 for ( k = 0; k < 4; k++ ){
23 t = ( t + a[ i ][ k ] * b[ k ][ j ] ) % m;
24 }
25 c[ i ][ j ] = t;
26 }
27 }
28}
29void MatrixPow( int n ){
30 if ( n == 1 ) return;
31 MatrixPow( n / 2 );
32 MatrixMulti( quo, quo, tmp );
33 if ( n % 2 ){
34 MatrixMulti( tmp, matrix, quo );
35 } else{
36 MatrixCopy( quo, tmp );
37 }
38}
39
40int main(){
41 int i, j, t;
42 while ( scanf("%d%d", &n, &m ) && n ){
43 ans[0]=1;ans[1]=1;ans[2]=5;ans[3]=11;
44 if ( n < 4 ){
45 printf("%d\n", ans[ n ] % m );
46 continue;
47 }
48 MatrixCopy( quo, matrix );
49 MatrixPow( n - 3 );
50 t = 0;
51 for ( i = 0; i < 4; i++ ){
52 t += ans[ i ] * quo[ i ][ 3 ];
53 }
54 printf("%d\n", t % m );
55 }
56}
57
还有一个我读过的所有程序中最新颖的(当然也可能是我孤陋寡闻了),让人觉得神清气爽的! 黄强写的程序!
1#include <stdio.h>
2#include <memory.h>
3int n,MOD;
4class Mat{
5public:
6 int v[4][4];
7 Mat(int x){
8 memset(v,0,sizeof(v));
9 if (x==1)
10 v[0][0]=v[1][1]=v[2][2]=v[3][3]=1;
11 else if (x==2){
12 v[0][0]=1; v[0][1]=5; v[0][2]=1; v[0][3]=-1;
13 v[1][0]=v[2][1]=v[3][2]=1;
14 }
15 }
16 Mat friend operator * (const Mat &A,const Mat &B){ //矩阵相乘
17 Mat C(0);
18 int i,j,k;
19 for (i=0;i<4;i++){
20 for (j=0;j<4;j++) {
21 for (k=0;k<4;k++)
22 C.v[i][j]=(C.v[i][j]+A.v[i][k]*B.v[k][j]%MOD)%MOD;
23 if (C.v[i][j]<0) C.v[i][j]+=MOD;
24 }
25 }
26 return C;
27 }
28};
29void solve() {
30 int ans;
31 Mat V(1),B(2);
32 while (n) {
33 if (n&1) V=V*B; //奇数
34 n>>=1; //除以2
35 B=B*B;
36 }
37 ans=11*V.v[3][0]+5*V.v[3][1]+V.v[3][2]+V.v[3][3];
38 ans%=MOD;
39 printf("%d\n",ans);
40}
41int main(){
42 while (scanf("%d%d",&n,&MOD)!=EOF && (n+MOD))
43 solve();
44 return 0;
45}
牛啊~~~
记录下来,没事就看看.这才是真正的ACM/ICPC!