为生存而奔跑
::
首页
::
联系
::
聚合
::
管理
271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks
留言簿
(5)
给我留言
查看公开留言
查看私人留言
我参与的团队
随笔分类
Algorithm(73)
C#(19)
Design Pattern(16)
Effective STL / C++ (12)
Information Retrival / Data Mining(13)
Java(25)
Linux kernel(2)
MFC(16)
Python(5)
TopCoder(1)
Ubuntu&Linux(56)
技术(12)
无聊(2)
杂(22)
随笔档案
2011年5月 (1)
2011年4月 (6)
2011年3月 (21)
2011年2月 (9)
2011年1月 (12)
2010年12月 (2)
2010年11月 (3)
2010年10月 (6)
2010年8月 (13)
2010年7月 (11)
2010年6月 (7)
2010年5月 (21)
2010年4月 (15)
2010年3月 (16)
2010年1月 (5)
2009年12月 (18)
2009年11月 (18)
2009年10月 (19)
2009年9月 (8)
2009年8月 (42)
2009年7月 (15)
2009年4月 (3)
相册
Girl
搜索
积分与排名
积分 - 324333
排名 - 74
最新评论
1. re: Invoke与BeginInvoke
讲得很好,清晰明了
--YJJ
2. re: Invoke与BeginInvoke
讲的这么好, 为啥没有人顶呢
--zhouandke
3. re: 数组分割问题
转载请注明
--呵呵
4. re: HDU 3415 单调队列
话说,sum数组为什么只开10W就能过,如果n=100000,k=100000,明显要开20W啊
--KissLL
5. re: GDB 单步调试
文章太强大了。
--kangear
阅读排行榜
1. GDB 单步调试(33295)
2. Emacs教程(20795)
3. 解决“windows无法连接到选定网络 网络可能不在区域中”(11448)
4. Invoke与BeginInvoke(9562)
5. Eclipse下搭建SWT开发环境(7957)
评论排行榜
1. C/C++没有数组(12)
2. HDU 3415 单调队列(8)
3. Ubuntu Linux常见中文输入法汇总(7)
4. word画图里自选图形里面的连接符不能用(5)
5. VMware Tools installation cannot be started manually while Easy Install is in progress.(3)
【矩阵问题】PKU 3070
pku 3070
题目要求计算Fibonacci数列的第n项最后4位。因为n可以很大(0 ≤
n
≤ 1,000,000,000)。因此直接计算在时限内是不可能的(有多个case)。题目还给出了计算的方法:表示成矩阵连乘的形式为
求第n项的后4位,相当于求第n项模10000的余数。而矩阵的乘法满足边乘边模。矩阵乘法还满足结合律,所以可以先计算出上面的一个矩阵的2的幂次方的值,记录下来。然后对于每一个n,将它表示成2进制。如当n=5时,只需计算一次矩阵乘法:1次方乘以4次方。当n=1000000000时最多只需计算29次矩阵乘法2^29 = 536870912)
#include
<
iostream
>
#include
<
algorithm
>
#include
<
string
>
#include
<
vector
>
#include
<
cmath
>
#include
<
map
>
using
namespace
std;
int
m[
31
][
4
],fact[
31
];
int
n;
void
init()
{
fact[
1
]
=
1
;
m[
1
][
0
]
=
1
; m[
1
][
1
]
=
1
; m[
1
][
2
]
=
1
; m[
1
][
3
]
=
0
;
for
(
int
i
=
2
;i
<=
30
;i
++
)
{
m[i][
0
]
=
(m[i
-
1
][
0
]
*
m[i
-
1
][
0
]
+
m[i
-
1
][
1
]
*
m[i
-
1
][
2
])
%
10000
;
m[i][
1
]
=
(m[i
-
1
][
0
]
*
m[i
-
1
][
1
]
+
m[i
-
1
][
1
]
*
m[i
-
1
][
3
])
%
10000
;
m[i][
2
]
=
(m[i
-
1
][
2
]
*
m[i
-
1
][
0
]
+
m[i
-
1
][
3
]
*
m[i
-
1
][
2
])
%
10000
;
m[i][
3
]
=
(m[i
-
1
][
2
]
*
m[i
-
1
][
1
]
+
m[i
-
1
][
3
]
*
m[i
-
1
][
3
])
%
10000
;
fact[i]
=
fact[i
-
1
]
*
2
;
}
}
void
solve()
{
bool
vis[
31
]
=
{
0
}
;
//
对n表示成2进制
for
(
int
i
=
30
;i
>
0
;i
--
)
if
(n
>=
fact[i])
{
n
-=
fact[i];
vis[i]
=
1
;
}
int
res[
4
]
=
{
1
,
0
,
0
,
1
}
;
//
单位矩阵
int
tmp[
4
];
for
(
int
i
=
1
;i
<=
30
;i
++
)
{
if
(vis[i])
{
tmp[
0
]
=
(res[
0
]
*
m[i][
0
]
+
res[
1
]
*
m[i][
2
])
%
10000
;
tmp[
1
]
=
(res[
0
]
*
m[i][
1
]
+
res[
1
]
*
m[i][
3
])
%
10000
;
tmp[
2
]
=
(res[
2
]
*
m[i][
0
]
+
res[
3
]
*
m[i][
2
])
%
10000
;
tmp[
3
]
=
(res[
2
]
*
m[i][
1
]
+
res[
3
]
*
m[i][
3
])
%
10000
;
for
(
int
j
=
0
;j
<
4
;j
++
)
res[j]
=
tmp[j];
}
}
printf(
"
%d\n
"
,res[
1
]);
}
int
main()
{
init();
while
(scanf(
"
%d
"
,
&
n)
!=
EOF
&&
n
!=-
1
)
{
solve();
}
}
posted on 2009-08-17 10:57
baby-fly
阅读(254)
评论(0)
编辑
收藏
引用
所属分类:
Algorithm
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
二分搜索 找上下界
算法导论上的归并排序
PKU 2184 dp
PKU 2392 多重背包
PKU 2823 Sliding Window 单调队列
HDU 3415 单调队列
t
CRecordSet
KMP字符串模式匹配详解
HDU 3450 树状数组 离散化
网站导航:
博客园
IT新闻
BlogJava
博问
Chat2DB
管理
Copyright @ baby-fly
Powered by:
.Text
and
ASP.NET
Theme by:
.NET Monster