轉(zhuǎn)自http://blog.csdn.net/wust_zzwh/article/details/52100392
基礎(chǔ)篇
數(shù)位dp是一種計數(shù)用的dp，一般就是要統(tǒng)計一個區(qū)間[le,ri]內(nèi)滿足一些條件數(shù)的個數(shù)。所謂數(shù)位dp袜匿，字面意思就是在數(shù)位上進行dp咯搀罢。數(shù)位還算是比較好聽的名字慷嗜，數(shù)位的含義：一個數(shù)有個位筐骇、十位录淡、百位删性、千位......數(shù)的每一位就是數(shù)位啦亏娜！
之所以要引入數(shù)位的概念完全就是為了dp。數(shù)位dp的實質(zhì)就是換一種暴力枚舉的方式蹬挺，使得新的枚舉方式滿足dp的性質(zhì)维贺，然后記憶化就可以了。
兩種不同的枚舉：對于一個求區(qū)間[le,ri]滿足條件數(shù)的個數(shù)巴帮，最簡單的暴力如下：

for(int i=le;i<=ri;i++)  
        if(right(i)) ans++;  

然而這樣枚舉不方便記憶化溯泣，或者說根本無狀態(tài)可言虐秋。
新的枚舉：控制上界枚舉，從最高位開始往下枚舉垃沦，例如：ri=213客给，那么我們從百位開始枚舉：百位可能的情況有0,1,2(覺得這里枚舉0有問題的繼續(xù)看)
然后每一位枚舉都不能讓枚舉的這個數(shù)超過上界213（下界就是0或者1，這個次要）肢簿，當百位枚舉了1靶剑，那么十位枚舉就是從0到9，因為百位1已經(jīng)比上界2小了池充，后面數(shù)位枚舉什么都不可能超過上界桩引。所以問題就在于：當高位枚舉剛好達到上界是，那么緊接著的一位枚舉就有上界限制了收夸。具體的這里如果百位枚舉了2坑匠，那么十位的枚舉情況就是0到1，如果前兩位枚舉了21卧惜，最后一位之是0到3(這一點正好對于代碼模板里的一個變量limit 專門用來判斷枚舉范圍)厘灼。最后一個問題：最高位枚舉0：百位枚舉0，相當于此時我枚舉的這個數(shù)最多是兩位數(shù)咽瓷，如果十位繼續(xù)枚舉0设凹，那么我枚舉的就是以為數(shù)咯，因為我們要枚舉的是小于等于ri的所以數(shù)忱详，當然不能少了位數(shù)比ri小的咯！(這樣枚舉是為了無遺漏的枚舉跺涤，不過可能會帶來一個問題匈睁，就是前導零的問題，模板里用lead變量表示桶错，不過這個不是每個題目都是會有影響的航唆，可能前導零不會影響我們計數(shù)，具體要看題目)
由于這種新的枚舉只控制了上界所以我們的Main函數(shù)總是這樣：

int main()  
{  
    long long le,ri;  
    while(~scanf("%lld%lld",&le,&ri))  
        printf("%lld\n",solve(ri)-solve(le-1));  
}  

w_w 是吧院刁！統(tǒng)計[1,ri]數(shù)量和[1,le-1]糯钙，然后相減就是區(qū)間[le,ri]的數(shù)量了，這里我寫的下界是1退腥，其實0也行任岸，反正相減后就沒了，注意題目中l(wèi)e的范圍都是大于等于1的(不然le=0,再減一就G_G了)
在講例題之前先講個基本的動態(tài)模板(先看后面的例題也行)：dp思想狡刘，枚舉到當前位置pos享潜，狀態(tài)為state(這個就是根據(jù)題目來的，可能很多嗅蔬，畢竟dp千變?nèi)f化)的數(shù)量(既然是計數(shù),dp值顯然是保存滿足條件數(shù)的個數(shù))

typedef long long ll;  
int a[20];  
ll dp[20][state];//不同題目狀態(tài)不同  
ll dfs(int pos,/*state變量*/,bool lead/*前導零*/,bool limit/*數(shù)位上界變量*/)//不是每個題都要判斷前導零  
{  
    //遞歸邊界剑按，既然是按位枚舉疾就，最低位是0，那么pos==-1說明這個數(shù)我枚舉完了  
    if(pos==-1) return 1;/*這里一般返回1艺蝴，表示你枚舉的這個數(shù)是合法的猬腰，那么這里就需要你在枚舉時必須每一位都要滿足題目條件，也就是說當前枚舉到pos位猜敢，一定要保證前面已經(jīng)枚舉的數(shù)位是合法的姑荷。不過具體題目不同或者寫法不同的話不一定要返回1 */  
    //第二個就是記憶化(在此前可能不同題目還能有一些剪枝)  
    if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];  
    /*常規(guī)寫法都是在沒有限制的條件記憶化，這里與下面記錄狀態(tài)是對應(yīng)锣枝，具體為什么是有條件的記憶化后面會講*/  
    int up=limit?a[pos]:9;//根據(jù)limit判斷枚舉的上界up;這個的例子前面用213講過了  
    ll ans=0;  
    //開始計數(shù)  
    for(int i=0;i<=up;i++)//枚舉厢拭，然后把不同情況的個數(shù)加到ans就可以了  
    {  
        if() ...  
        else if()...  
        ans+=dfs(pos-1,/*狀態(tài)轉(zhuǎn)移*/,lead && i==0,limit && i==a[pos]) //最后兩個變量傳參都是這樣寫的  
        /*這里還算比較靈活，不過做幾個題就覺得這里也是套路了 
        大概就是說撇叁，我當前數(shù)位枚舉的數(shù)是i供鸠，然后根據(jù)題目的約束條件分類討論 
        去計算不同情況下的個數(shù)，還有要根據(jù)state變量來保證i的合法性陨闹，比如題目 
        要求數(shù)位上不能有62連續(xù)出現(xiàn),那么就是state就是要保存前一位pre,然后分類楞捂， 
        前一位如果是6那么這意味就不能是2，這里一定要保存枚舉的這個數(shù)是合法*/  
    }  
    //計算完趋厉，記錄狀態(tài)  
    if(!limit && !lead) dp[pos][state]=ans;  
    /*這里對應(yīng)上面的記憶化寨闹，在一定條件下時記錄，保證一致性君账，當然如果約束條件不需要考慮lead繁堡，這里就是lead就完全不用考慮了*/  
    return ans;  
}  
ll solve(ll x)  
{  
    int pos=0;  
    while(x)//把數(shù)位都分解出來  
    {  
        a[pos++]=x%10;//個人老是喜歡編號為[0,pos),看不慣的就按自己習慣來，反正注意數(shù)位邊界就行  
        x/=10;  
    }  
    return dfs(pos-1/*從最高位開始枚舉*/,/*一系列狀態(tài) */,true,true);//剛開始最高位都是有限制并且有前導零的乡数，顯然比最高位還要高的一位視為0嘛  
}  
int main()  
{  
    ll le,ri;  
    while(~scanf("%lld%lld",&le,&ri))  
    {  
        //初始化dp數(shù)組為-1,這里還有更加優(yōu)美的優(yōu)化,后面講  
        printf("%lld\n",solve(ri)-solve(le-1));  
    }  
}  

相信讀者還對這個有不少疑問椭蹄，筆者認為有必要講一下記憶化為什么是if(!limit)才行，大致就是說有無limit會出現(xiàn)狀態(tài)沖突净赴，舉例：
約束：數(shù)位上不能出現(xiàn)連續(xù)的兩個1(11绳矩、112、211都是不合法的)
假設(shè)就是[1,210]這個區(qū)間的個數(shù)
狀態(tài):dp[pos][pre]:當前枚舉到pos位玖翅，前面一位枚舉的是pre(更加前面的位已經(jīng)合法了)翼馆，的個數(shù)(我的pos從0開始)
先看錯誤的方法計數(shù)，就是不判l(wèi)imit就是直接記憶化
那么假設(shè)我們第一次枚舉了百位是0金度，顯然后面的枚舉limit=false应媚，也就是數(shù)位上0到9的枚舉，然后當我十位枚舉了1猜极，此時考慮dp[0][1],就是枚舉到個位珍特，前一位是1的個數(shù)，顯然dp[0][1]=9;(個位只有是1的時候是不滿足的)魔吐，這個狀態(tài)記錄下來扎筒，繼續(xù)dfs莱找，一直到百位枚舉了2，十位枚舉了1嗜桌，顯然此時遞歸到了pos=0,pre=1的層奥溺，而dp[0][1]的狀態(tài)已經(jīng)有了即dp[pos][pre]!=-1；此時程序直接return dp[0][1]了骨宠，然而顯然是錯的浮定，因為此時是有l(wèi)imit的個位只能枚舉0，根本沒有9個數(shù)层亿，這就是狀態(tài)沖突了桦卒。有l(wèi)ead的時候可能出現(xiàn)沖突，這只是兩個最基本的不同的題目可能還要加限制匿又，反正宗旨都是讓dp狀態(tài)唯一
對于這個錯誤說兩點：一是limit為true的數(shù)并不多方灾，一個個枚舉不會很浪費時間，所以我們記錄下! limit的狀態(tài)解決了不少子問題重疊碌更。第二裕偿，有人可能想到把dp狀態(tài)改一下dp[pos][state][limit]就是分別記錄不同limit下的個數(shù)，這種方法一般是對的痛单，關(guān)于這個具體會講嘿棘，下面有題bzoj3209會用到這個。
數(shù)位的部分就是這些旭绒，然后就是難點鸟妙，dp部分，dp大牛的藝術(shù)挥吵，弱雞只能看看+...+
既然從高位往低位枚舉重父，那么狀態(tài)一般都是與前面已經(jīng)枚舉的數(shù)位有關(guān)并且通常是根據(jù)約束條件當前枚舉的這一位能使得狀態(tài)完整(比如一個狀態(tài)涉及到連續(xù)k位，那么就保存前k-1的狀態(tài)蔫劣，當前枚舉的第k個是個恰好湊成成一個完整的狀態(tài)坪郭，不過像那種狀態(tài)是數(shù)位的和就直接保存前綴和為狀態(tài)了)个从，不過必然有一位最簡單的一個狀態(tài)dp[pos]當前枚舉到了pos位脉幢。dp部分就要開始講例題了，不過會介紹幾種常用防tle的優(yōu)化嗦锐。
實戰(zhàn)篇
例一：HDU 2089 不要62
入門題嫌松。就是數(shù)位上不能有4也不能有連續(xù)的62，沒有4的話在枚舉的時候判斷一下奕污，不枚舉4就可以保證狀態(tài)合法了萎羔，所以這個約束沒有記憶化的必要，而對于62的話碳默，涉及到兩位贾陷，當前一位是6或者不是6這兩種不同情況我計數(shù)是不相同的缘眶，所以要用狀態(tài)來記錄不同的方案數(shù)。
dp[pos][sta]表示當前第pos位髓废，前一位是否是6的狀態(tài)巷懈，這里sta只需要去0和1兩種狀態(tài)就可以了，不是6的情況可視為同種慌洪，不會影響計數(shù)顶燕。

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<string>  
using namespace std;  
typedef long long ll;  
int a[20];  
int dp[20][2];  
int dfs(int pos,int pre,int sta,bool limit)  
{  
    if(pos==-1) return 1;  
    if(!limit && dp[pos][sta]!=-1) return dp[pos][sta];  
    int up=limit ? a[pos] : 9;  
    int tmp=0;  
    for(int i=0;i<=up;i++)  
    {  
        if(pre==6 && i==2)continue;  
        if(i==4) continue;//都是保證枚舉合法性  
        tmp+=dfs(pos-1,i,i==6,limit && i==a[pos]);  
    }  
    if(!limit) dp[pos][sta]=tmp;  
    return tmp;  
}  
int solve(int x)  
{  
    int pos=0;  
    while(x)  
    {  
        a[pos++]=x%10;  
        x/=10;  
    }  
    return dfs(pos-1,-1,0,true);  
}  
int main()  
{  
    int le,ri;  
    //memset(dp,-1,sizeof dp);可優(yōu)化  
    while(~scanf("%d%d",&le,&ri) && le+ri)  
    {  
        memset(dp,-1,sizeof dp);  
        printf("%d\n",solve(ri)-solve(le-1));  
    }  
    return 0;  
}  

入門就不多講了，開始講常用優(yōu)化吧冈爹！
第一:memset(dp,-1,sizeof dp);放在多組數(shù)據(jù)外面涌攻。
這一點是一個數(shù)位特點振愿，使用的條件是：約束條件是每個數(shù)自身的屬性乌企，而與輸入無關(guān)。
具體的：上一題不要62和4瓢对，這個約束對每一個數(shù)都是確定的剂买，就是說任意一個數(shù)滿不滿足這個約束都是確定惠爽，比如444這個數(shù)，它不滿足約束條件瞬哼，不管你輸入的區(qū)間是多少你都無法改變這個數(shù)不滿足約束這個事實婚肆，這就是數(shù)自身的屬性（我們每組數(shù)據(jù)只是在區(qū)間計數(shù)而已，只能說你輸入的區(qū)間不包含444的話坐慰，我們就不把它統(tǒng)計在內(nèi)较性，而無法改變?nèi)魏问聦崳?br> 由此，我們保存的狀態(tài)就可以一直用(注意還有要limit结胀，不同區(qū)間是會影響數(shù)位在有限制條件下的上限的)
這點優(yōu)化就不給具體題目了赞咙，這個還有進一步的擴展。不過說幾個我遇到的簡單的約束：
1.求數(shù)位和是10的倍數(shù)的個數(shù),這里簡化為數(shù)位sum%10這個狀態(tài)糟港，即dp[pos][sum]這里10 是與多組無關(guān)的攀操，所以可以memset優(yōu)化，不過注意如果題目的模是輸入的話那就不能這樣了秸抚。
2.求二進制1的數(shù)量與0的數(shù)量相等的個數(shù)速和，這個也是數(shù)自身的屬性。
3.剥汤。颠放。。吭敢。碰凶。
還是做題積累吧。搞懂思想！
下面介紹的方法就是要行memset優(yōu)化欲低，把不滿足前提的通過修改辕宏，然后優(yōu)化。
介紹之前,先說一種較為笨拙的修改砾莱，那就是增加狀態(tài)匾效，前面講limit的地方說增加一維dp[pos][state][limit]，能把不同情況下狀態(tài)分別記錄(不過這個不能memset放外面)恤磷∶婧撸基于這個思想，我們考慮：約束為數(shù)位是p的倍數(shù)的個數(shù)扫步，其中p數(shù)輸入的魔策，這和上面sum%10類似，但是dp[pos][sum]顯然已經(jīng)不行了河胎，每次p可能都不一樣闯袒，為了強行把memset提到外面加狀態(tài)dp[pos][sum][p]，對于每個不同p分別保存對應(yīng)的狀態(tài)游岳。這里前提就比較簡單了政敢，你dp數(shù)組必須合法，p太大就G_G了胚迫。所以對于與輸入有關(guān)的約束都可以強行增加狀態(tài)(這并不代表能ac喷户，如果題目數(shù)據(jù)少的話就隨便你亂搞了)
第二：相減。
例題：HDU 4734
題目給了個f(x)的定義：F(x) = An

• 2n-1

• An-1

• 2n-2

• ... + A2

• 2 + A1
• 1访锻，Ai是十進制數(shù)位褪尝，然后給出a,b求區(qū)間[0,b]內(nèi)滿足f(i)<=f(a)的i的個數(shù)。
  常規(guī)想：這個f(x)計算就和數(shù)位計算是一樣的期犬，就是加了權(quán)值河哑，所以dp[pos][sum]，這狀態(tài)是基本的龟虎。a是題目給定的璃谨，f(a)是變化的不過f(a)最大好像是4600的樣子。如果要memset優(yōu)化就要加一維存f(a)的不同取值鲤妥，那就是dp[10][4600][4600]佳吞，這顯然不合法。
  這個時候就要用減法了旭斥，dp[pos][sum]容达，sum不是存當前枚舉的數(shù)的前綴和(加權(quán)的)古涧，而是枚舉到當前pos位垂券，后面還需要湊sum的權(quán)值和的個數(shù)，
  也就是說初始的是時候sum是f(a),枚舉一位就減去這一位在計算f(i)的權(quán)值，那么最后枚舉完所有位 sum>=0時就是滿足的菇爪，后面的位數(shù)湊足sum位就可以了算芯。
  仔細想想這個狀態(tài)是與f(a)無關(guān)的(新手似乎很難理解)，一個狀態(tài)只有在sum>=0時才滿足凳宙，如果我們按常規(guī)的思想求f(i)的話熙揍，那么最后sum>=f(a)才是滿足的條件。

#include<cstdio>  
#include<cstring>  
#include<iostream>  
#include<string>  
  
using namespace std;  
const int N=1e4+5;  
int dp[12][N];  
int f(int x)  
{  
    if(x==0) return 0;  
    int ans=f(x/10);  
    return ans*2+(x%10);  
}  
int all;  
int a[12];  
int dfs(int pos,int sum,bool limit)  
{  
    if(pos==-1) {return sum<=all;}  
    if(sum>all) return 0;  
    if(!limit && dp[pos][all-sum]!=-1) return dp[pos][all-sum];  
    int up=limit ? a[pos] : 9;  
    int ans=0;  
    for(int i=0;i<=up;i++)  
    {  
        ans+=dfs(pos-1,sum+i*(1<<pos),limit && i==a[pos]);  
    }  
    if(!limit) dp[pos][all-sum]=ans;  
    return ans;  
}  
int solve(int x)  
{  
    int pos=0;  
    while(x)  
    {  
        a[pos++]=x%10;  
        x/=10;  
    }  
    return dfs(pos-1,0,true);  
}  
int main()  
{  
    int a,ri;  
    int T_T;  
    int kase=1;  
    scanf("%d",&T_T);  
    memset(dp,-1,sizeof dp);  
    while(T_T--)  
    {  
        scanf("%d%d",&a,&ri);  
        all=f(a);  
        printf("Case #%d: %d\n",kase++,solve(ri));  
    }  
    return 0;  
}  

減法的藝術(shù)Ｊ仙＝烨簟！

例題 POJ 3252
這題的約束就是一個數(shù)的二進制中0的數(shù)量要不能少于1的數(shù)量是尖，通過上一題意系，這題狀態(tài)就很簡單了，dp[pos][num],到當前數(shù)位pos,0的數(shù)量減去1的數(shù)量為num的方案數(shù)饺汹，一個簡單的問題蛔添，中間某個pos位上num可能為負數(shù)(這不一定是非法的，因為我還沒枚舉完嘛兜辞，只要最終的num>=0才能判合法迎瞧，中途某個pos就不一定了)，這里比較好處理逸吵，Hash嘛凶硅，最小就-32吧(好像),直接加上32，把32當0用扫皱。這題主要是要想講一下lead的用法咏尝，顯然我要統(tǒng)計0的數(shù)量，前導零是有影響的啸罢。至于!lead&&!limit才能dp编检，都是類似的，自己慢慢體會吧扰才。

#pragma comment(linker, "/STACK:10240000,10240000")  
#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<string>  
#include<queue>  
#include<set>  
#include<vector>  
#include<map>  
#include<stack>  
#include<cmath>  
#include<algorithm>  
using namespace std;  
const double R=0.5772156649015328606065120900;  
const int N=1e5+5;  
const int mod=1e9+7;  
const int INF=0x3f3f3f3f;  
const double eps=1e-8;  
const double pi=acos(-1.0);  
typedef long long ll;  
int dp[35][66];  
int a[66];  
int dfs(int pos,int sta,bool lead,bool limit)  
{  
    if(pos==-1)  
        return sta>=32;  
    if(!limit && !lead && dp[pos][sta]!=-1) return dp[pos][sta];  
    int up=limit?a[pos]:1;  
    int ans=0;  
    for(int i=0;i<=up;i++)  
    {  
        if(lead && i==0) ans+=dfs(pos-1,sta,lead,limit && i==a[pos]);//有前導零就不統(tǒng)計在內(nèi)  
        else ans+=dfs(pos-1,sta+(i==0?1:-1),lead && i==0,limit && i==a[pos]);  
    }  
    if(!limit && !lead ) dp[pos][sta]=ans;  
    return ans;  
}  
int solve(int x)  
{  
    int pos=0;  
    while(x)  
    {  
        a[pos++]=x&1;  
        x>>=1;  
    }  
    return dfs(pos-1,32,true,true);  
}  
int main()  
{  
    memset(dp,-1,sizeof dp);  
    int a,b;  
    while(~scanf("%d%d",&a,&b))  
    {  
        printf("%d\n",solve(b)-solve(a-1));  
    }  
    return 0;  
}  

然后就是一些需要自己yy的題：
HDU 3709 這題就是要枚舉中軸允懂，然后數(shù)位dp
UVA 1305 這題我二分然后數(shù)位dp搞(好像不是正解，我水過的)
Hbzoj 1799 這題講一下：
（偷偷告訴你衩匣，這個oj是單組測試蕾总，然后memset什么的都是浮云了）
*約束：一個數(shù)是它自己數(shù)位和的倍數(shù)，直接dp根本找不到狀態(tài)琅捏，枚舉數(shù)位和生百，因為總就162,然后問題就變成了一個數(shù)%mod=0，mod是枚舉的柄延，想想狀態(tài)：dp[pos][sum][val]蚀浆，當前pos位上數(shù)位和是sum,val就是在算這個數(shù)%mod,（從高位算 10+i），因為我們枚舉的數(shù)要保證數(shù)位和等于mod，還要保證這個數(shù)是mod的倍數(shù)市俊，很自然就能找到這些狀態(tài)杨凑，顯然對于每一個mod，val不能保證狀態(tài)唯一摆昧，這是你要是想加一維dp[pos][sum][val][mod],記錄每一個mod的狀態(tài)(這里sum可以用減法撩满，然而val不行，就只能加一維)绅你，那你就想太多了伺帘，這樣是會超時的(因為狀態(tài)太多，記憶化效果不好)忌锯。這里直接對每一個mod曼追，memset一次就能ac。下面的代碼還把limit的當做了狀態(tài)汉规，因為每次都要初始化礼殊，所以能這樣，memset在多組外面是不能這樣的针史，不過奇葩的晶伦，這代碼，如果不把limit當狀態(tài)啄枕，還是在!limit 條件下記錄dp婚陪，提交一發(fā)，時間竟然更短了频祝，可能是每次memset的關(guān)系Ｃ诓巍！常空！

#include<cstdio>  
#include<cstring>  
#include<iostream>  
#include<string>  
  
using namespace std;  
  
typedef long long ll;  
  
ll dp[20][163][163][2];  
int a[20];  
ll dfs(int pos,int sum,int val,int mod,bool limit)  
{  
    if(sum-9*pos-9>0) return 0;//最壞的情況沽一，這一位及后面的全部為9都不能達到0那就直接GG，這個剪枝不會影響ac  
    if(pos==-1) return sum==0 && val==0;  
    if(dp[pos][sum][val][limit]!=-1) return dp[pos][sum][val][limit];  
    int up=limit?a[pos]:9;  
    ll ans=0;  
    for(int i=0;i<=up;i++)  
    {  
        if(sum-i<0) break;  
        ans+=dfs(pos-1,sum-i,(val*10+i)%mod,mod,limit && i==a[pos]);  
    }  
    dp[pos][sum][val][limit]=ans;  
    return ans;  
}  
ll solve(ll x)  
{  
    int pos=0;  
    while(x)  
    {  
        a[pos++]=x%10;  
        x/=10;  
    }  
    ll ans=0;  
    for(int i=1;i<=pos*9;i++)//上限就是每一位都是9  
    {  
        memset(dp,-1,sizeof dp);  
        ll tmp=dfs(pos-1,i,0,i,true);  
        ans+=tmp;  
    }  
    return ans;  
}  
int main()  
{  
//    cout<<18*9<<endl;  
    ll le,ri;  
//    memset(dp,-1,sizeof dp);  
    while(~scanf("%lld%lld",&le,&ri))  
        printf("%lld\n",solve(ri)-solve(le-1));  
    return 0;  
}  
/* 
1 1000000000000000000 
*/  

基本講的差不多了漓糙。前段時間學了點新東西Ｏ巢！

新的領(lǐng)域--計數(shù)轉(zhuǎn)求和
HDU 4507
這題麻煩就是要求數(shù)的平方和昆禽。
我們先考慮求和的問題蝗蛙，一個區(qū)間，數(shù)位dp能在一些約束下計數(shù)醉鳖，現(xiàn)在要這些數(shù)的和捡硅。其實組合數(shù)學搞搞就可以了：如 現(xiàn)在枚舉的某一位pos,我統(tǒng)計了這一位枚舉i的滿足條件的個數(shù)cnt，其實只要算i對總和的貢獻就可以了盗棵，對于一個數(shù)而言第pos位是i壮韭，那么對求和貢獻就是i10^pos,就是十進制的權(quán)值北发，然后有cnt個數(shù)都滿足第pos位是i，最后sum=cnti10^pos.原理就是這樣平方和可以看做(a10^pos+b)2,a是你當前pos位要枚舉的泰涂，b其實是個子問題，就是pos之后的位的貢獻值辐怕，把這個平方展開就可以了逼蒙！

#pragma comment(linker, "/STACK:10240000,10240000")  
#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<string>  
#include<queue>  
#include<set>  
#include<vector>  
#include<map>  
#include<stack>  
#include<cmath>  
#include<algorithm>  
using namespace std;  
const double R=0.5772156649015328606065120900;  
const int N=1e5+5;  
const int mod=1e9+7;  
const int INF=0x3f3f3f3f;  
const double eps=1e-8;  
const double pi=acos(-1.0);  
typedef long long ll;  
ll fact[20];  
void init()  
{  
    fact[0]=1;  
    for(int i=1;i<20;i++)  
        fact[i]=fact[i-1]*10%mod;  
}  
struct node  
{  
    ll cnt,sum,sqr;  
    node(ll cnt=-1,ll sum=0,ll sqr=0):cnt(cnt),sum(sum),sqr(sqr){}  
}dp[20][7][7];  
int a[20];  
ll fac(ll x)  
{  
    return x*x%mod;  
}  
ll dfs(int pos,ll num,ll val,ll&cnt,ll&sum,bool limit)  
{  
    if(pos==-1) {  
        if(num==0 || val==0)  
            return 0;  
        cnt=1;  
        return 0;  
    }  
    if(!limit && dp[pos][num][val].cnt!=-1) {  
            cnt=dp[pos][num][val].cnt;  
            sum=dp[pos][num][val].sum;  
            return dp[pos][num][val].sqr;  
    }  
    int up=limit?a[pos]:9;  
    ll sq=0;  
    for(int i=0;i<=up;i++)  
    if(i!=7)  
    {  
        ll cn=0,su=0;  
        ll tmp=dfs(pos-1,(num+i)%7,(val*10+i)%7,cn,su,limit && i==a[pos]);  
        ll tm=i*fact[pos]%mod;  
        tmp=(tmp+fac(tm)*cn%mod+(tm*su%mod)*2%mod)%mod;//計數(shù)之后要更新sum,sqr  
        sum=(sum+su+(i*fact[pos]%mod)*cn%mod)%mod;  
        cnt=(cnt+cn)%mod;  
        sq=(sq+tmp)%mod;  
    }  
    if(!limit) dp[pos][num][val]=node(cnt,sum,sq);  
    return sq;  
}  
ll solve(ll x)  
{  
    int pos=0;  
    while(x)  
    {  
        a[pos++]=x%10;  
        x/=10;  
    }  
    ll t1=0,t2=0;  
    return dfs(pos-1,0,0,t1,t2,true);  
}  
bool judge(ll x)  
{  
    int sum=0;  
    int pos=0;  
    if(x%7==0) return false;  
    while(x)  
    {  
        if(x%10==7) return false;  
        sum+=x%10;  
        x/=10;  
    }  
    sum%=7;  
    return sum!=0;  
}  
int main()  
{  
    init();  
    for(int i=0;i<20;i++)  
        for(int j=0;j<7;j++)  
        for(int k=0;k<7;k++)//memset  
    {  
        dp[i][j][k].cnt=-1;  
        dp[i][j][k].sum=0;  
        dp[i][j][k].sqr=0;  
    }  
    int T_T;  
    scanf("%d",&T_T);  
    while(T_T--)  
    {  
        ll le,ri;  
        scanf("%I64d%I64d",&le,&ri);  
        ll ans=solve(ri)-solve(le-1);  
        ans=(ans%mod+mod)%mod;  
        printf("%I64d\n",ans);  
    }  
    return 0;  
}  

做題去~~