A Coin Problem(矩阵快速幂 入门水题)
时间限制:3000 ms | 内存限制:65535 KB
描述
One day,Jiameier is tidying up the room,and find some coins. Then she throws the coin to play.Suddenly,she thinks of a problem ,that if throw n times coin ,how many situations of no-continuous up of the coin. Hey,Let's solve the problem.

输入
The first of input is an integer T which stands for the number of test cases. For each test case, there is one integer n (1<=n<=1000000000) in a line, indicate the times of throwing coins.
输出
The number of all situations of no-continuous up of the coin, moduled by 10000.
样例输入
3
1
2
3
样例输出
2
3
5
来源
SCU Programming Contest 2011 Preliminary
额开始一看到题目就赶紧是递推。。。。然后再试一试 脑袋里面出现了一个想法
把硬币分为正面朝上(1) 和 背面朝上(0) 2种情况
然后想到了 用动态规划来解决问题。。。

dp[i][0]=dp[i][1]+dp[i][0]
dp[i][1]=dp[i][0]

额 不过 看到数据很大。。。刚刚接触动态规划 还没入门额。。。胆子小
没敢用 脑袋抽风了。。。 突然发现 这竟然是Fibonacci数列哈
额 数据量挺大的 但是对10000求模。。。
于是有了用矩阵快速幂解决问题的想法
同时涛哥说用找循环节因为数不大。。
(哎。。 一下午 万老板的题目一道做不出来啊。。。。涛哥发现南阳理那哪里有玩的 遂群起聚之)
矩阵快速幂以后有时间再写详细的方法。。
对于这道题 先构建一个2X2矩阵
|0 1|=A
|1 1|
然后 利用{f[0],f[1]}*A^n={f[n],f[n-1]}
p.s. 矩阵快速幂用到了二分的想法哦(很多小算法往往是很有用的支柱,知识需要结合在一起0.0)

#include
#include
const int MAX=10000;
int A[1][2];
int B[2][2]={0,1,1,1};
int C[2][2];
void mul(int a[][2],int b[][2],int c[][2]){//功能,求出a*b存在c里
    int i,j,h;
    for(i=0;i&lt;2;i++)
        for(j=0;j&lt;2;j++){
            c[i][j]=0;
            for(h=0;h&lt;2;h++)
                c[i][j]+=a[i][h]*b[h][j];
            c[i][j]%=MAX;
        }
}
void qiu(int x,int a[][2]){//求出 B 的x次方,存在a里
    int i,j;
    int b[2][2];
    if(x==1){//x等于1时,直接把B存在a里
        for(i=0;i&lt;2;i++)
            for(j=0;j&lt;2;j++)
                a[i][j]=B[i][j];
        return;
    }
    if(x%2==0){
        qiu(x/2,b);
        mul(b,b,a);
    }
    else{
        qiu(x-1,b);
        mul(b,B,a);
    }
}
int main(){
    int c[2][2];
    int i,j,h,l,p,n,N;
    scanf("%d",&N);
    while(N--){
        scanf("%d",&p);
        A[0][0]=1;A[0][1]=1;
        qiu(p+1,C);
        mul(A,C,c);
        n=c[0][0]%MAX;
        printf("%d\n",n);
    }
    return 0;
}

涛神的找循环节的码(突然感觉短小精湛哈~)

#include
int ans[100000];
int main(void) {
   int t;

   ans[1] = 2;
   ans[2] = 3;
   ans[3] = 5;
   ans[4] = 8;
   for (int i=5; i&lt;=20000; ++i) {
      ans[i] = (ans[i-2] + ans[i-1]) % 10000;
 //    if (ans[i] == 8&&ans[i-1]==5&&ans[i-2]==3&&ans[i-3]==2) {
 //       printf("%dn", i);
 //        printf("%dn", ans[i-3]);
 //        printf("%dn", ans[i-2]);
 //        printf("%dn", ans[i-1]);
 //        printf("%dn", ans[i]);
 //      }
    }

   scanf("%d", &t);
   while (t--) {
      int n;
      scanf("%d", &n);
      n %= 1500;
      if (n==0) {
         n = 1500;
      }
      printf("%d\n", ans[n]);
   }
   return 0;
}
原创文章采用 CC BY-NC-SA 4.0协议 进行许可,转载请著名转自: nyist698 A Coin Problem 矩阵快速幂

0 评论