【OpenJudge9270】【Pku2440】【递推】DNA
DNA
【描述】
A kind of virus has attacked the X planet, and many lives are infected. After weeks of study, The CHO (Creature Healthy Organization) of X planet finally finds out that this kind of virus has two kind of very simple DNA, and can be represented by 101 and 111. Unfortunately, the lives on the planet also have DNA formed by 0s and 1s. If a creature's DNA contains the virus' DNA, it will be affected; otherwise it will not. Given an integer L, it is clear that there will be 2 ^ L different lives, of which the length of DNA is L. Your job is to find out in the 2 ^ L lives how many won't be affected?
【输入】
The input contains several test cases. For each test case it contains a positive integer L (1 <= L <= 10 ^ 6). The end of input is indicated by end-of-file.
【输出】
For each test case, output K mod 2005, here K is the number of lives that will not be affected.
【样例输入】
4
【样例输出】
9
【Solution】
根据题意,111、101是不合法的,所以我们
令f1[i]为长度为i且结尾三个数是的所有合法01串数量,
令f2[i]为长度为i且结尾三个数是的所有合法01串数量,
令f3[i]为长度为i且结尾三个数是的所有合法01串数量,
令f4[i]为长度为i且结尾三个数是的所有合法01串数量,
令f5[i]为长度为i且结尾三个数是的所有合法01串数量,
令f6[i]为长度为i且结尾三个数是的所有合法01串数量。
设目前长度为n。我们发现000的后两位、100的后两位和f1[n]的最后三位的前两位相等,而多出来的一位有两种情况0和1,选择符合f1[n]最后一位的就行,方案数不变,这样就把f1[n]的最后三位凑全了,f1[n]便可以从f1[n-1]和f5[n-1]转移来。所以f1[n]=f1[n-1]+f5[n-1]。
以此类推:
f2[n]=f1[n-1]+f5[n-1]
f3[n]·=f2[n-1]
f4[n]=f2[n-1]
f5[n]=f3[n-1]+f6[n-1]
f6[n]=f4[n-1]
令dp[n]=f1[n]+f2[n]+f3[n]+f4[n]+f5[n]+f6[n]。下面就是激(奇)动(技)人(淫)心(巧)的数学推导了:
dp[n]=f1[n]+f2[n]+f3[n]+f4[n]+f5[n]+f6[n]
=f1[n-1]+f5[n-1]+f1[n-1]+f5[n-1]+f2[n-1]+f2[n-1]+f3[n-1]+f6[n-1]+f4[n-1]
=dp[n-1]+f3[n-2]+f6[n-2]+f1[n-2]+f5[n-2]+f1[n-2]+f5[n-2]
=dp[n-1]+f2[n-3]+f4[n-3]+f1[n-3]+f5[n-3]+f3[n-3]+f6[n-3]+f1[n-3]+f5[n-3]+f3[n-3]+f6[n-3]
=dp[n-1]+dp[n-3]+f1[n-3]+f5[n-3]+f3[n-3]+f6[n-3]
=dp[n-1]+dp[n-3]+f1[n-4]+f5[n-4]+f3[n-4]+f6[n-4]+f2[n-4]+f4[n-4]
=dp[n-1]+dp[n-3]+dp[n-4]
#include <cstdio>
int N;
int dp[];
int main(){
scanf("%d",&N); dp[]=; dp[]= ;dp[]=; dp[]=;
for(int i=;i<=N;++i) dp[i]=(dp[i-]%+dp[i-]%+dp[i-]%)%;
printf("%d",dp[N]);
return ;
}
最新文章
- HBase 安装
- PHP中cookie与session总结
- windows 8 metro 开发学习资源链接
- 为什么要用on()而不直接使用click
- 深入理解GCD ( 二 )
- MVC4中使用SignalR
- 十一、oracle 数据库管理员
- 洛谷P2480 [SDOI2010]古代猪文
- 【BZOJ1821】[JSOI2010]部落划分(二分,并查集)
- Gym.101908 Brazil Subregional Programming Contest(寒假自训第六场)
- eclipce连接数据库增删改查
- Vue(七):computed计算属性
- JAVA-JSP内置对象之response对象
- python各类项目模块记录
- 题目1004:Median(qsort函数自定义cmp函数)
- padding 扩大边距 margin-top 与页面顶部的距离 hover鼠标移动到上面出现背景色CSS
- as3 加载库声音报错
- 判定一个数num是否为x的幂
- Ruby中Time的常用函数
- 关于C语言底层