之前做數位統計時，一般是先初始化，然后再逐位統計。
   前幾天在codeforces遇到一種用記憶化搜索寫的數位統計，挺神奇的。用它改寫之前寫過的幾道數位統計，發現代碼更短，速度也更快，有一定通用性.
   這種寫法一般用于初始化跟逐位統計是一樣過程的。
        
        codeforces 55D
        http://www.shnenglu.com/Yuan/archive/2011/01/24/139201.html
      
        我是從這題了解到這種寫法
             
        用這種方法寫，一個流程是，列出式子(pre*10^pos + next)  pre是確定的，next是變量
      所以參數就為pre,pos加上一些其他的，還有一個標記doing，表示是計算有上界限制的還是沒有上界限制（所有情況，即end=9）   
      dfs(pos-1 , npre , doing && i ==end)
      
      2010成都賽區A題  zoj 3416
      之前的寫法 http://www.shnenglu.com/Yuan/archive/2010/11/14/133608.html
      改寫后
      

/**//*
    題目描述見另外一份
    平衡，即∑a[i]*(i-o) = 0   o為支點
    對于一個數，支點o是唯一的，所以不會有重復計數的情況（但有一種特殊的，就是0,00,000等都是一樣的，會計算多次，
    最后減去即可）
    假設檢查到pos處，對于上面的式子∑a[i]*(i-o) = 0，這里確定了支點為o
    之前的數其∑a[i]*(i-o)的結果為pre
    所以參數需要為pos , o , pre 

    當檢查到pos=-1時，return pre == 0
    否則，看當前是計算所有情況還是具體情況(doing)
    如果是所有情況且dp值!=-1，直接return
    否則就枚舉0到end
    
    而支點o需要在最外層枚舉出來
*/
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

long long dp[19][19][2000];
int digit[19];

void init()
{
    memset(dp,-1,sizeof(dp));
}

long long dfs(int pos , int o , int pre , bool doing)
{
    if(pos == -1)
        return pre == 0;

    if(!doing && dp[pos][o][pre] != -1)
        return dp[pos][o][pre];

    long long ans = 0;
    int end = doing ? digit[pos] : 9;
    for(int i = 0 ; i <= end ; i ++)
    {
        int npre = pre;
        npre += (pos-o)*i;
        ans += dfs(pos-1 , o , npre , doing && i == end);
    }

    if(!doing)
        dp[pos][o][pre] = ans;
    return ans;
}

long long cal(long long x)
{
    int pos = 0;
    while(x)
    {
        digit[pos++] = x % 10;
        x /= 10;         
    }
    long long ans = 0;
    for(int o = 0 ; o < pos ; o ++)
    {
        ans += dfs(pos-1 , o , 0 , 1);
    }
    return  ans - (pos-1);//duplicate 0
}

int main()
{
    init();
    int T;
    for(scanf("%d",&T) ; T--; )
    {
        long long left , right;
        scanf("%lld%lld",&left , &right);
        printf("%lld\n",cal(right) - cal(left - 1));
    }
    return 0;
}

      2010 成都網絡賽 B  hdu 3652
      之前的代碼 http://www.shnenglu.com/Yuan/archive/2010/09/23/127454.html
      

/**//*
    求[1,n]內有多少個數字，該數字有13，且能被13整除   n<=10^9
    
    x % 13 = 0
    (pre*10^pos + next) % 13 = 0   pre是之前確定的部分
    需要的參數為pre , pos , 狀態have
    have記錄pre擁有"13"，pos+1位為"1"，沒有"13"   分別用have = 2,1,0表示
    
    然后記憶化搜索

*/
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int dp[10][13][3];
int digit[10];

__int64 dfs(int pos , int pre , int have , bool doing)
{
    if(pos == -1)
        return have == 2 && pre == 0;

    if(!doing && dp[pos][pre][have] != -1)
        return dp[pos][pre][have];

    int ans = 0;
    int end = doing ? digit[pos] : 9;
    for(int i = 0 ; i <= end ; i ++)
    {
        int npre = (pre*10 + i) % 13;
        int nhave = have;
        if(have == 0 && i == 1)
            nhave = 1;
        else if(have == 1 && i != 1)
            nhave = 0;
        if(have == 1 && i == 3)
            nhave = 2;
        ans += dfs(pos-1 , npre , nhave , doing && i == end );
    }

    if(!doing)
        dp[pos][pre][have] = ans;
    return ans;
}


int cal(int x)
{
    int pos = 0;
    while(x)
    {
        digit[pos++] = x % 10;
        x /= 10;
    }
    return dfs(pos - 1 , 0 , 0 , 1);
}

int main()
{
    memset(dp,-1,sizeof(dp));
    int n;
    while(~scanf("%d",&n))
        printf("%d\n",cal(n));
    return 0;
}

      參數跟條件有關，就像hdu3555就不需要pre

         hdu 3555
       之前寫法 http://www.shnenglu.com/Yuan/archive/2010/10/24/131057.html
         

/**//*
    問[1,n]內有多少個數字包含"49"
    這里用記憶化搜索
    更加好寫，而且快

    hdu 3652 是加強版
*/
#include<cstdio>
#include<algorithm>

using namespace std;


__int64 dp[20][3];
int digit[20];

__int64 dfs(int pos , int have , bool doing)
{
    if(pos == -1)
        return have == 2;

    if(!doing && dp[pos][have] !=-1)
        return dp[pos][have];

    __int64 ans = 0;
    int end = doing ? digit[pos] : 9;
    for(int i = 0 ; i <= end; i++)
    {
        int nhave = have;        
        if(have == 1 && i != 4)
            nhave = 0;
        if(have == 0 && i == 4)
            nhave = 1;
        if(have == 1 && i == 9)
            nhave = 2;
        ans += dfs(pos-1 , nhave , doing && i == end);
    }
    
    if(!doing)
    {
        dp[pos][have] = ans;
    }

    return ans;
}

__int64 cal(__int64 x)
{
    int pos = 0;
    while(x)
    {
        digit[pos++] = x % 10;
        x /= 10;
    }
    return dfs(pos - 1  , 0 , 1);
}

int main()
{
    memset(dp,-1,sizeof(dp));
    int T;
    for(scanf("%d",&T) ; T-- ;)
    {
            __int64 n;
            scanf("%I64d",&n);
            printf("%I64d\n",cal(n));
    }
    return 0;
}