“红色病毒”问题
时间限制：1000 ms | 内存限制：65535 KB 难度：4- 描述
-
医学研究者最近发现了一种新病毒，因为其蔓延速度与曾经在Internet上传播的“红色代码”不相上下，故被称为“红色病毒”。 经研究发现，该病毒及其变种的DNA序列中，腺嘌呤（A）、胞嘧啶（C）均是成对出现的。LYH想知道在这种特征下，所有可能成为该病毒的DNA序列的个数。
- 输入
- 多组测试数据。 每组数据输入一个整数n，表示该病毒DNA序列的长度。（1≤n≤10^9） n=0时表示输入结束，不用做任何处理。
- 输出
- 每组输出占一行，代表该病毒长度为n的所有可能的DNA序列个数。由于结果可能非常大，你只需输出对10007取余后的结果即可。
- 样例输入
-
12
- 样例输出
-
26
- 提示
- DNA序列仅由腺嘌呤（A)，鸟嘌呤（G），胞嘧啶（C），胸腺嘧啶（T）四种核苷酸组成。 当n=2时，所有可能的DNA序列为TT、TG、GT、GG、AA、CC。
-
-
- 分析：因为题目要求A和C要成对出现，即A和C的数量都是偶数，所以可以定义4个状态：
- dp[n][0]表示长度为n时A的数量为偶数，C的数量也为偶数，
- dp[n][1]表示长度为n时A的数量为偶数，C的数量为奇数，
- dp[n][2]表示长度为n时A的数量为奇数，C的数量为偶数，
- dp[n][3]表示长度为n时A的数量为奇数，C的数量也为奇数的DNA序列的数量，
- 则
- dp[n][0] = dp[n-1][0] * 2 + dp[n-1][1] * 1 + dp[n-1][2] * 1 + dp[n-1][3] * 0
- dp[n][1] = dp[n-1][0] * 1 + dp[n-1][1] * 2 + dp[n-1][2] * 0 + dp[n-1][3] * 1
- dp[n][2] = dp[n-1][0] * 1 + dp[n-1][1] * 0 + dp[n-1][2] * 2 + dp[n-1][3] * 1
- dp[n][3] = dp[n-1][0] * 0 + dp[n-1][1] * 1 + dp[n-1][2] * 1 + dp[n-1][3] * 2
- 根据这个递推关系，可以构造出如下一个4*4的矩阵，
- | 2 1 1 0 |
- | 1 2 0 1 |
- | 1 0 2 1 |
- | 0 1 1 2 |
-
然后利用矩阵快速幂就可以快速求出答案。
#include#include #define mod 10007 struct Matrix { int mat[4][4]; Matrix() { memset(mat, 0, sizeof(mat)); for(int i = 0; i < 4; i++) mat[i][i] = 1; } }; Matrix Multi(Matrix a, Matrix b) { Matrix res; for(int i = 0; i < 4; i++) { for(int j = 0; j < 4; j++) { res.mat[i][j] = 0; for(int k = 0; k < 4; k++) { res.mat[i][j] += a.mat[i][k] * b.mat[k][j]; res.mat[i][j] %= mod; } } } return res; } Matrix Pow(Matrix a, int x) { Matrix res; while(x) { if(x&1) res = Multi(res, a); a = Multi(a, a); x >>= 1; } return res; } int main() { int T, n; Matrix A; //系数矩阵 A.mat[0][0] = 2; A.mat[0][1] = 1; A.mat[0][2] = 1; A.mat[0][3] = 0; A.mat[1][0] = 1; A.mat[1][1] = 2; A.mat[1][2] = 0; A.mat[1][3] = 1; A.mat[2][0] = 1; A.mat[2][1] = 0; A.mat[2][2] = 2; A.mat[2][3] = 1; A.mat[3][0] = 0; A.mat[3][1] = 1; A.mat[3][2] = 1; A.mat[3][3] = 2; scanf("%d",&T); while(T--) { scanf("%d", &n); Matrix ans = Pow(A, n); printf("%d\n", ans.mat[0][0]); } return 0; }
- <script type="text/java script">BAIDU_CLB_fillSlot("771048");
- 点击复制链接 与好友分享! 回本站首页 <script> function copyToClipBoard(){ var clipBoardContent=document.title + '\r\n' + document.location; clipBoardContent+='\r\n'; window.clipboardData.setData("Text",clipBoardContent); alert("恭喜您！复制成功"); }
<script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)]; - 您对本文章有什么意见或着疑问吗？请到 论坛讨论您的关注和建议是我们前行的参考和动力??
- 相关文章
- <script type="text/java script">BAIDU_CLB_fillSlot("182716");
- <script type="text/java script">BAIDU_CLB_fillSlot("517916");
- 图文推荐
