BNUOJ 4359 无爱的编号（一个不错的DP ）

题目大意：http://gnu.bnu.edu.cn/contest/problem_show.php?pid=4359

Description

 众所周知，拉手网有许多客户，由于客户数量实在过于庞大，因此拉手网希望为每位客户进行编号以便更好的为客户服务。每个编号为一个由 ‘0’~‘9’组成的N位数字。考虑到很多人不喜欢数字4和数字13，因此我们称包含4或包含13的编号为无爱编号，如134、84、121351都是无 爱编号，123则不是无爱编号。现在我们希望知道，所有N位的编号中，刨除掉无爱编号后剩余的编号数量。这个编号数量可能很大，我们只要知道结果的最后8 位即可。

Input

 输入的第一行是一个整数T，表示数据组数。

Output

 对于每组数据，输出一个8位整数表示编号数量的最后8位。若编号数量不足8位则用前导零填充。


题目分析： 唉，比赛的时候一个劲的往组合数学方面写，最后郁闷死掉了 ，用组合数学写，貌似太难了 ，至少我不会，没写出来，后来看了解题报告，终于 终于。。。恍然大悟 。原来是一道简单的 dp， 由于对dp 不是很敏感，所以当时没相当 状态转移方程，汗颜呐
看看题目吧：

这里我们用dp[i][0] 表示 前 i 位不包含 4与 13的编号数目 且最后一位不是1 ， dp[i][1] 表示 前 i 位不包含4 与 13的 编号数目，但最后一位是1！

然后我们得到方程：

        dp[i][0] = 8*dp[i-1][0]+7*dp[i-1][1]   // 前 i -1位 合法的但最后位不为1的编号后面可以填 8个数字，（除去 1与4 因为4是
                                                                      非 法的 、dp[i][0]最后位不能为1,） ,前i-1 位合法，但最后一位是1的， 我们只能
                                                                      在其后面填 其他7个数字 得到新的合法编号（除去1 ，3， 4）

        dp[i][1]=dp[i-1][0] + dp[i-1][1];      // 这里在第i位 填1 不会构成不合法编号，所以只要把前面 i-1位的所有情况加起来就可以

                                                                  可以了   
最后一步只要

                            total[i]=dp[i][0]+dp[i][1]  就是我们要求的总的方案数，

代码：

#include<iostream>
#include<cstdio>
using namespace std;
int num[1000100][2];
int main(){
	num[0][0]=1;
	num[0][1]=0;
	for(int i=1;i<=1000000;i++){
		num[i][0]=(8*num[i-1][0]+7*num[i-1][1])%100000000;
		num[i][1]=(num[i-1][0]+num[i-1][1])%100000000;
	}
	int cas,n,ans;
	scanf("%d",&cas);
	while(cas--){
		scanf("%d",&n);
		printf("%08d\n",(num[n][0]+num[n][1])%100000000);
	}
	return 0;
}