ccf201312-4有趣的数，递推

http://115.28.138.223/view.page?gpid=T2

0在1之前，2在3之前，0123至少出现一次。由题意开头的数只能是2。

从最高位开始，一位一位的递推，不过需要递推多个情况来得出结论。

根据条件，第i位（i>0）可能出现的情况有：

以此得到递推公式。

另外，可以通过数列的相关知识，求得一个f[i]关于i的公式，将算法的复杂度直接从O(n)降到O(1)，这大概才是最佳的答案吧。

题目得到的结果比较大，可以边加边求余，不影响结果。

C语言代码

#include <stdio.h>

long long a,b,c,d,e,f;
long long ta,tb,tc,td,te,tf;

int main(){
    int i=0,num;
    a=b=c=d=e=f=g=h=0;

    a++;//第一位为2
    scanf("%d",&num);
    for(i=1;i<num;i++){//从第二位开始求解，循环num-1次
        //ta=a;
        tb=b+b+a;
        tc=c+a;
        td=d+d+b;
        te=e+e+c+b;
        tf=f+f+d+e;


        //a=ta%1000000007LL;
        b=tb%1000000007LL;
        c=tc%1000000007LL;
        d=td%1000000007LL;
        e=te%1000000007LL;
        f=tf%1000000007LL;
    }
    printf("%d",f);
}

ccf201312-4有趣的数，递推

原文：http://blog.csdn.net/frto027/article/details/51364510