#8779. 有趣的数

有趣的数

问题描述   我们把一个数称为有趣的,当且仅当:  
 1. 它的数字只包含0, 1, 2, 3,且这四个数字都出现过至少一次。  
 2. 所有的0都出现在所有的1之前,而所有的2都出现在所有的3之前。  
 3. 最高位数字不为0。  
 因此,符合我们定义的最小 的 有趣的数 是2013。除此以外,4位的有趣的数还有两个:2031和2301。  
 请计算恰好有n 位的有趣的数的个数。由于答案可能非常大,只需要输出答案除以1000000007的余数。
输入格式   
输入只有一行,包括恰好一个正整数n (4 ≤ n ≤ 1000)。
输出格式   
输出只有一行,包括恰好n 位的整 数中有趣的数的个数除以1000000007的余数。
样例输入
4
样例输出
3

问题描述:参见上文。

问题分析:这是一个计算问题,关键在于找到一个递推式。只要找到一个递推式,问题就解决了。有时候这类问题也用DP(动态规划)来解决。

根据题意,有趣的数满足以下约束条件如下:

1.只包含数字0、1、2和3

2.0、1、2和3各自至少出现一次

3.所有的0都出现在1之前

4.所有的2都出现在3之前

5.最高位数字不为0

数(字符串)可以分为以下六种情况(或称为状态):

1.只包含数字2,记为S1

2.只包含数字2和0(0开始的数0个,以此数为前缀的数均不是以0开始),记为S2

3.只包含数字2和3,记为S3

4.只包含数字2、0和1,并且满足所有0在1之前,记为S4

5.只包含数字2、0和3,并且满足所有2在3之前,记为S5

6.包含任意数字(包含0、1、2和3),满足所有0在1之前,满足所有2在3之前,记为S6

考虑递推式:

1.对于S1,考虑其长度l,定义f(l,S1)为长度l的S1数的数量,则f(l,S1)=1。也就是说长度为l的只包含2的数只有1个。

2.对于S2,考虑其长度l,定义f(l,S2)为长度l的S2数的数量,当l=1则那么f(l,S2)=0,即f(1,S2)=0,当l>1则f(l,S2)=f(l-1,S2)*2+f(l-1,S1)。这是因为,长度为l的S2数可以是由长度为l-1的S2的数加上2或0构成,例20为长度为2的S2数,那么202和200为长度为3的S2数;另外,长度为l的S2数可以是由长度为l-1的S1的数加上0构成,例如22为长度为2的S1数,那么220为长度为3的S2数。

3.对于S3,考虑其长度l,定义f(l,S3)为长度l的S3数的数量,当l=1则那么f(l,S3)=0,即那么f(1,S3)=0,当l>1则f(l,S3)=f(l-1,S3)*2+f(l-1,S1)。这是因为,长度为l的S3数可以是由长度为l-1的S3的数加上2或3构成,例23为长度为2的S3数,那么232和233为长度为3的S3数;另外,长度为l的S3数可以是由长度为l-1的S1的数加上3构成,例如22为长度为2的S1数,那么223为长度为3的S3数。

4.对于S4,考虑其长度l,定义f(l,S4)为长度l的S4数的数量,当l=1则那么f(l,S4)=0,即f(1,S4)=0,当l>1则f(l,S4)=f(l-1,S4)*2+f(l-1,S2)+f(l-1,S3)。这是因为,长度为l的S4数可以是由长度为l-1的S4的数加上2或1构成(满足所有0在1之前,不可以加上0),例201为长度为3的S4数,那么2012和2011为长度为4的S4数;另外,长度为l的S4数可以是由长度为l-1的S2的数加上1构成,例如20为长度为2的S2数,那么201为长度为3的S4数。

同理,对于S5和S6,可以得到相应的递推公式。详细参见以下的源程序。

有了递推式,程序就可以根据递推式,逐步进行计算。

Limitation

1s, 1024KiB for each test case.