求fibonacci數%n,典型的矩陣應用，二分求fibonacci數模一個數，f[0][0]%n 即為所求
代碼：
1 #include<cstdio>
2 #include<iostream>
3 #include<cmath>
4 #include<cstring>
5
6 using namespace std;
7
8 unsigned long long N = 0;
9 struct Mat
10 {
11 unsigned long long mat[2][2];
12 Mat operator * (Mat &b)
13 {
14 Mat tmp;
15 memset(tmp.mat,0,sizeof(tmp.mat));
16 for(int i = 0; i < 2; ++i)
17 {
18 for(int j = 0; j < 2; ++j)
19 {
20 for(int k = 0; k < 2; ++k)
21 {
22 tmp.mat[i][j] += mat[i][k] * b.mat[k][j];
23 }
24 if(tmp.mat[i][j] > N) tmp.mat[i][j] %= N;
25 }
26 }
27 return tmp;
28 }
29 Mat pow(int k)
30 {
31 if(k == 0)
32 {
33 mat[0][0] = mat[1][1] = 1;
34 mat[0][1] = mat[1][0] = 0;
35 return *this;
36 }
37 else if(k == 1) return *this;
38 else
39 {
40 Mat tmp;
41 tmp = *this * (*this);
42 if(k & 1) return tmp.pow(k/2) * (*this);
43 else return tmp.pow(k/2);
44 }
45 }
46 };
47 unsigned long long n,m;
48 int main()
49 {
50 while(cin >> n >> m)
51 {
52 if(n == 0) cout << "0" << endl;
53 else
54 {
55 N = 1<<m;
56 Mat f;
57 f.mat[0][0] = f.mat[0][1] = f.mat[1][0] = 1;
58 f.mat[1][1] = 0;
59 f = f.pow(n-1);
60 cout << f.mat[0][0]%N << endl;
61 }
62 }
63 return 0;
64 }
還可以根據循環節做：
1 #include<cstdio>
2 #include<iostream>
3 using namespace std;
4 long long f[2000000];
5 int main()
6 {
7 int n , m;
8 while(cin >> n >> m)
9 {
10 f[0] = 0; f[1] = 1;
11 long long N = 1<<m;
12 int i;
13 for(i = 2; i <= n; ++i)
14 {
15 f[i] = (f[i-1] % N + f[i-2] % N) % N;
16 if(f[i] == 1 && f[i-1] == 0) break;
17 }
18 if(i > n) cout << f[n] << endl;
19 else cout << f[n % (i - 1)] << endl;
20 }
21 return 0;
22 }
23
蔡神代碼
1 #include <iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<cstring>
5 using namespace std;
6 typedef long long ll;
7 ll dp[1000];
8
9 ll hash(ll t,ll n)
10 {
11 return t*4+n%4;
12 }
13
14 ll f(ll n,ll m,ll cur)
15 {
16 if(n<3)
17 return 1%m;
18 ll u=hash(cur,n);
19 if(dp[u]>-1)
20 return dp[u];
21 ll i=n/2;
22 ll f1=f(i,m,cur+1);
23 ll f2=f(n-i-1,m,cur+1);
24 ll f3=f(i+1,m,cur+1);
25 ll f4=f(n-i,m,cur+1);
26 return dp[u]=((f1*f2)%m+(f3*f4)%m)%m;
27 }
28
29 int main()
30 {
31 ll m,n;
32 while(scanf("%lld%lld",&n,&m)!=EOF)
33 {
34 memset(dp,-1,sizeof(dp));
35 printf("%lld\n",n?f(n,1<<m,0):0);
36 }
37 return 0;
38 }
posted on 2011-11-06 00:31
ACSeed 閱讀(311)
評論(0) 編輯 收藏 引用