POJ 3070 这个为矩阵相乘的基础题。

建议做矩阵相乘时先做3070,后面在开始做3233,3623,2440.3623和2440我还没开始做,今天下午就要自己做出来!!!!还有。。。海贼王更新了!!!!
 1 #include<iostream>
 2 using namespace std;
 3 //===================================================
 4 int k;
 5 struct Point 
 6 {
 7     int a[2][2];
 8     void init()
 9     {
10         a[0][0]=1;a[0][1]=1;
11         a[1][0]=1;a[1][1]=0;
12     }
13 };
14 
15 Point mul(Point p,Point q)//矩阵相乘
16 {
17     int i,j;
18     Point c;
19     for(i=0;i<2;++i)
20     {
21         for(int j=0;j<2;++j)
22         {
23             int sum=0;
24             for(int k=0;k<2;++k)
25             {
26                 sum+=(p.a[i][k]*q.a[k][j])%10000;
27             /*    if(sum>10000)
28                 {
29                     sum-=10000;
30                 }*/
31                 c.a[i][j]=sum%10000;
32             }
33         }
34      }
35     return c;
36 }
37 
38 Point maxtrimul(Point s,int k)
39 {
40     Point ans;
41     ans=s;
42     if(k==1)return s;
43     ans=maxtrimul(s,k>>1);
44     ans=mul(ans,ans);
45     if(k&1)
46     {
47         ans=mul(s,ans);//切记!!!!
48     }
49     return ans;
50     
51 
52 }
53 
54 int main()
55 {
56     Point s;
57     s.init();
58     Point c;
59     while(cin>>k&&k!=-1)
60     {
61         if(k==0)
62         {
63             cout<<0<<endl;
64             continue;
65         }
66         if(k==1)
67         {
68             cout<<1<<endl;
69             continue;
70         }
71         c=maxtrimul(s,k);
72         cout<<(c.a[0][1]%10000)<<endl;
73         continue;
74 
75     }
76 }

posted on 2011-11-27 11:54 四也 阅读(218) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年11月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜