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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int matrix[4][4] =
{
{0,0,0,-1},
3![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{1,0,0,1},
4![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{0,1,0,5},
5![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{0,0,1,1}};
6
int n, m;
7
int tmp[4][4], quo[4][4], ans[4];
8![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
9![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void MatrixCopy( int to[][4], int from[][4] )
{
10
int i, j;
11![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for ( i = 0; i < 4; i++ )
{
12![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for ( j = 0; j < 4; j++ )
{
13
to[ i ][ j ] = from[ i ][ j ];
14
}
15
}
16
}
17![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void MatrixMulti( int a[][4], int b[][4], int c[][4] )
{
18
int i, j, k, t;
19![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for ( i = 0; i < 4; i++ )
{
20![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for ( j = 0; j < 4; j++ )
{
21
t = 0;
22![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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
}
29![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void MatrixPow( int n )
{
30
if ( n == 1 ) return;
31
MatrixPow( n / 2 );
32
MatrixMulti( quo, quo, tmp );
33![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if ( n % 2 )
{
34
MatrixMulti( tmp, matrix, quo );
35![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
} else
{
36
MatrixCopy( quo, tmp );
37
}
38
}
39![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
40![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
41
int i, j, t;
42![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while ( scanf("%d%d", &n, &m ) && n )
{
43
ans[0]=1;ans[1]=1;ans[2]=5;ans[3]=11;
44![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for ( i = 0; i < 4; i++ )
{
52
t += ans[ i ] * quo[ i ][ 3 ];
53
}
54
printf("%d\n", t % m );
55
}
56
}
57![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
还有一个我读过的所有程序中最新颖的(当然也可能是我孤陋寡闻了),让人觉得神清气爽的! 黄强写的程序!
1
#include <stdio.h>
2
#include <memory.h>
3
int n,MOD;
4![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
class Mat
{
5
public:
6
int v[4][4];
7![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
Mat friend operator * (const Mat &A,const Mat &B)
{ //矩阵相乘
17
Mat C(0);
18
int i,j,k;
19![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i=0;i<4;i++)
{
20![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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
};
29![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void solve()
{
30
int ans;
31
Mat V(1),B(2);
32![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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
}
41![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
42
while (scanf("%d%d",&n,&MOD)!=EOF && (n+MOD))
43
solve();
44
return 0;
45
}
牛啊~~~
记录下来,没事就看看.这才是真正的ACM/ICPC!