Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

本人的一种解法。。。。。

Posted by pengshihui at 2010-09-24 10:38:35 on Problem 2440
(以下 n 均大于 2 ):
设 f(n) 为 2^n 个基因中感染了病毒的个数,则 2^n - f(n) 即为此题的解
设 a(n) 为基因长度为 n 时未感染病毒的基因中以 00 结束的基因的个数
设 b(n) 为基因长度为 n 时未感染病毒的基因中以 01 结束的基因的个数
设 c(n) 为基因长度为 n 时未感染病毒的基因中以 10 结束的基因的个数
设 d(n) 为基因长度为 n 时未感染病毒的基因中以 11 结束的基因的个数
则不难推出:
f(n+1)=2*f(n)+c(n)+d(n);
a(n+1)=a(n)+c(n);
b(n+1)=a(n);
c(n+1)=b(n)+d(n);
d(n+1)=b(n);
定义 m(n) 矩阵如下:
	m(n)=[f(n),a(n),b(n),c(n),d(n)],(n=3,4,5,.....)
设存在一个矩阵 K 为:
	2 0 0 0 0
	0 1 1 0 0
	0 0 0 1 1
	1 1 0 0 0
	1 0 0 1 0
则用矩阵 m(n) 右乘矩阵 k 可以得到以下矩阵:
	[f(n+1),a(n+1),b(n+1),c(n+1),d(n+1)],此矩阵即为 m(n+1);
所以有 m(n)=m(3)*k^(n-3);
我们不难算出 m(3)=[2,2,1,2,1],而 k^(n-3)用快速幂运算可以在 O( log( n-3 )*5^3 )得出答案。。此题圆满解决。。。。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator