Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
本人的一种解法。。。。。(以下 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator