轉(zhuǎn)自http://blog.csdn.net/wust_zzwh/article/details/52100392
基礎(chǔ)篇
數(shù)位dp是一種計(jì)數(shù)用的dp，一般就是要統(tǒng)計(jì)一個(gè)區(qū)間[le,ri]內(nèi)滿足一些條件數(shù)的個(gè)數(shù)。所謂數(shù)位dp，字面意思就是在數(shù)位上進(jìn)行dp咯。數(shù)位還算是比較好聽的名字，數(shù)位的含義：一個(gè)數(shù)有個(gè)位、十位、百位、千位......數(shù)的每一位就是數(shù)位啦！
之所以要引入數(shù)位的概念完全就是為了dp。數(shù)位dp的實(shí)質(zhì)就是換一種暴力枚舉的方式，使得新的枚舉方式滿足dp的性質(zhì)，然后記憶化就可以了。
兩種不同的枚舉：對于一個(gè)求區(qū)間[le,ri]滿足條件數(shù)的個(gè)數(shù)，最簡單的暴力如下：
for(int i=le;i<=ri;i++)
if(right(i)) ans++;
然而這樣枚舉不方便記憶化，或者說根本無狀態(tài)可言。
新的枚舉：控制上界枚舉，從最高位開始往下枚舉，例如：ri=213，那么我們從百位開始枚舉：百位可能的情況有0,1,2(覺得這里枚舉0有問題的繼續(xù)看)
然后每一位枚舉都不能讓枚舉的這個(gè)數(shù)超過上界213（下界就是0或者1，這個(gè)次要），當(dāng)百位枚舉了1，那么十位枚舉就是從0到9，因?yàn)榘傥?已經(jīng)比上界2小了，后面數(shù)位枚舉什么都不可能超過上界。所以問題就在于：當(dāng)高位枚舉剛好達(dá)到上界是，那么緊接著的一位枚舉就有上界限制了。具體的這里如果百位枚舉了2，那么十位的枚舉情況就是0到1，如果前兩位枚舉了21，最后一位之是0到3(這一點(diǎn)正好對于代碼模板里的一個(gè)變量limit 專門用來判斷枚舉范圍)。最后一個(gè)問題：最高位枚舉0：百位枚舉0，相當(dāng)于此時(shí)我枚舉的這個(gè)數(shù)最多是兩位數(shù)，如果十位繼續(xù)枚舉0，那么我枚舉的就是以為數(shù)咯，因?yàn)槲覀円杜e的是小于等于ri的所以數(shù)，當(dāng)然不能少了位數(shù)比ri小的咯！(這樣枚舉是為了無遺漏的枚舉，不過可能會帶來一個(gè)問題，就是前導(dǎo)零的問題，模板里用lead變量表示，不過這個(gè)不是每個(gè)題目都是會有影響的，可能前導(dǎo)零不會影響我們計(jì)數(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)計(jì)[1,ri]數(shù)量和[1,le-1]，然后相減就是區(qū)間[le,ri]的數(shù)量了，這里我寫的下界是1，其實(shí)0也行，反正相減后就沒了，注意題目中l(wèi)e的范圍都是大于等于1的(不然le=0,再減一就G_G了)
在講例題之前先講個(gè)基本的動(dòng)態(tài)模板(先看后面的例題也行)：dp思想，枚舉到當(dāng)前位置pos，狀態(tài)為state(這個(gè)就是根據(jù)題目來的，可能很多，畢竟dp千變?nèi)f化)的數(shù)量(既然是計(jì)數(shù),dp值顯然是保存滿足條件數(shù)的個(gè)數(shù))
typedef long long ll;
int a[20];
ll dp[20][state];//不同題目狀態(tài)不同
ll dfs(int pos,/*state變量*/,bool lead/*前導(dǎo)零*/,bool limit/*數(shù)位上界變量*/)//不是每個(gè)題都要判斷前導(dǎo)零
{
//遞歸邊界，既然是按位枚舉，最低位是0，那么pos==-1說明這個(gè)數(shù)我枚舉完了
if(pos==-1) return 1;/*這里一般返回1，表示你枚舉的這個(gè)數(shù)是合法的，那么這里就需要你在枚舉時(shí)必須每一位都要滿足題目條件，也就是說當(dāng)前枚舉到pos位，一定要保證前面已經(jīng)枚舉的數(shù)位是合法的。不過具體題目不同或者寫法不同的話不一定要返回1 */
//第二個(gè)就是記憶化(在此前可能不同題目還能有一些剪枝)
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;這個(gè)的例子前面用213講過了
ll ans=0;
//開始計(jì)數(shù)
for(int i=0;i<=up;i++)//枚舉，然后把不同情況的個(gè)數(shù)加到ans就可以了
{
if() ...
else if()...
ans+=dfs(pos-1,/*狀態(tài)轉(zhuǎn)移*/,lead && i==0,limit && i==a[pos]) //最后兩個(gè)變量傳參都是這樣寫的
/*這里還算比較靈活，不過做幾個(gè)題就覺得這里也是套路了
大概就是說，我當(dāng)前數(shù)位枚舉的數(shù)是i，然后根據(jù)題目的約束條件分類討論
去計(jì)算不同情況下的個(gè)數(shù)，還有要根據(jù)state變量來保證i的合法性，比如題目
要求數(shù)位上不能有62連續(xù)出現(xiàn),那么就是state就是要保存前一位pre,然后分類，
前一位如果是6那么這意味就不能是2，這里一定要保存枚舉的這個(gè)數(shù)是合法*/
}
//計(jì)算完，記錄狀態(tài)
if(!limit && !lead) dp[pos][state]=ans;
/*這里對應(yīng)上面的記憶化，在一定條件下時(shí)記錄，保證一致性，當(dāng)然如果約束條件不需要考慮lead，這里就是lead就完全不用考慮了*/
return ans;
}
ll solve(ll x)
{
int pos=0;
while(x)//把數(shù)位都分解出來
{
a[pos++]=x%10;//個(gè)人老是喜歡編號為[0,pos),看不慣的就按自己習(xí)慣來，反正注意數(shù)位邊界就行
x/=10;
}
return dfs(pos-1/*從最高位開始枚舉*/,/*一系列狀態(tài) */,true,true);//剛開始最高位都是有限制并且有前導(dǎo)零的，顯然比最高位還要高的一位視為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));
}
}
相信讀者還對這個(gè)有不少疑問，筆者認(rèn)為有必要講一下記憶化為什么是if(!limit)才行，大致就是說有無limit會出現(xiàn)狀態(tài)沖突，舉例：
約束：數(shù)位上不能出現(xiàn)連續(xù)的兩個(gè)1(11、112、211都是不合法的)
假設(shè)就是[1,210]這個(gè)區(qū)間的個(gè)數(shù)
狀態(tài):dp[pos][pre]:當(dāng)前枚舉到pos位，前面一位枚舉的是pre(更加前面的位已經(jīng)合法了)，的個(gè)數(shù)(我的pos從0開始)
先看錯(cuò)誤的方法計(jì)數(shù)，就是不判l(wèi)imit就是直接記憶化
那么假設(shè)我們第一次枚舉了百位是0，顯然后面的枚舉limit=false，也就是數(shù)位上0到9的枚舉，然后當(dāng)我十位枚舉了1，此時(shí)考慮dp[0][1],就是枚舉到個(gè)位，前一位是1的個(gè)數(shù)，顯然dp[0][1]=9;(個(gè)位只有是1的時(shí)候是不滿足的)，這個(gè)狀態(tài)記錄下來，繼續(xù)dfs，一直到百位枚舉了2，十位枚舉了1，顯然此時(shí)遞歸到了pos=0,pre=1的層，而dp[0][1]的狀態(tài)已經(jīng)有了即dp[pos][pre]!=-1；此時(shí)程序直接return dp[0][1]了，然而顯然是錯(cuò)的，因?yàn)榇藭r(shí)是有l(wèi)imit的個(gè)位只能枚舉0，根本沒有9個(gè)數(shù)，這就是狀態(tài)沖突了。有l(wèi)ead的時(shí)候可能出現(xiàn)沖突，這只是兩個(gè)最基本的不同的題目可能還要加限制，反正宗旨都是讓dp狀態(tài)唯一
對于這個(gè)錯(cuò)誤說兩點(diǎn)：一是limit為true的數(shù)并不多，一個(gè)個(gè)枚舉不會很浪費(fèi)時(shí)間，所以我們記錄下! limit的狀態(tài)解決了不少子問題重疊。第二，有人可能想到把dp狀態(tài)改一下dp[pos][state][limit]就是分別記錄不同limit下的個(gè)數(shù)，這種方法一般是對的，關(guān)于這個(gè)具體會講，下面有題bzoj3209會用到這個(gè)。
數(shù)位的部分就是這些，然后就是難點(diǎn)，dp部分，dp大牛的藝術(shù)，弱雞只能看看+...+
既然從高位往低位枚舉，那么狀態(tài)一般都是與前面已經(jīng)枚舉的數(shù)位有關(guān)并且通常是根據(jù)約束條件當(dāng)前枚舉的這一位能使得狀態(tài)完整(比如一個(gè)狀態(tài)涉及到連續(xù)k位，那么就保存前k-1的狀態(tài)，當(dāng)前枚舉的第k個(gè)是個(gè)恰好湊成成一個(gè)完整的狀態(tài)，不過像那種狀態(tài)是數(shù)位的和就直接保存前綴和為狀態(tài)了)，不過必然有一位最簡單的一個(gè)狀態(tài)dp[pos]當(dāng)前枚舉到了pos位。dp部分就要開始講例題了，不過會介紹幾種常用防tle的優(yōu)化。
實(shí)戰(zhàn)篇
例一：HDU 2089 不要62
入門題。就是數(shù)位上不能有4也不能有連續(xù)的62，沒有4的話在枚舉的時(shí)候判斷一下，不枚舉4就可以保證狀態(tài)合法了，所以這個(gè)約束沒有記憶化的必要，而對于62的話，涉及到兩位，當(dāng)前一位是6或者不是6這兩種不同情況我計(jì)數(shù)是不相同的，所以要用狀態(tài)來記錄不同的方案數(shù)。
dp[pos][sta]表示當(dāng)前第pos位，前一位是否是6的狀態(tài)，這里sta只需要去0和1兩種狀態(tài)就可以了，不是6的情況可視為同種，不會影響計(jì)數(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ù)外面。
這一點(diǎn)是一個(gè)數(shù)位特點(diǎn)，使用的條件是：約束條件是每個(gè)數(shù)自身的屬性，而與輸入無關(guān)。
具體的：上一題不要62和4，這個(gè)約束對每一個(gè)數(shù)都是確定的，就是說任意一個(gè)數(shù)滿不滿足這個(gè)約束都是確定，比如444這個(gè)數(shù)，它不滿足約束條件，不管你輸入的區(qū)間是多少你都無法改變這個(gè)數(shù)不滿足約束這個(gè)事實(shí)，這就是數(shù)自身的屬性（我們每組數(shù)據(jù)只是在區(qū)間計(jì)數(shù)而已，只能說你輸入的區(qū)間不包含444的話，我們就不把它統(tǒng)計(jì)在內(nèi)，而無法改變?nèi)魏问聦?shí)）。
由此，我們保存的狀態(tài)就可以一直用(注意還有要limit，不同區(qū)間是會影響數(shù)位在有限制條件下的上限的)
這點(diǎn)優(yōu)化就不給具體題目了，這個(gè)還有進(jìn)一步的擴(kuò)展。不過說幾個(gè)我遇到的簡單的約束：
1.求數(shù)位和是10的倍數(shù)的個(gè)數(shù),這里簡化為數(shù)位sum%10這個(gè)狀態(tài)，即dp[pos][sum]這里10 是與多組無關(guān)的，所以可以memset優(yōu)化，不過注意如果題目的模是輸入的話那就不能這樣了。
2.求二進(jìn)制1的數(shù)量與0的數(shù)量相等的個(gè)數(shù)，這個(gè)也是數(shù)自身的屬性。
3.。。。。。
還是做題積累吧。搞懂思想！
下面介紹的方法就是要行memset優(yōu)化，把不滿足前提的通過修改，然后優(yōu)化。
介紹之前,先說一種較為笨拙的修改，那就是增加狀態(tài)，前面講limit的地方說增加一維dp[pos][state][limit]，能把不同情況下狀態(tài)分別記錄(不過這個(gè)不能memset放外面)?；谶@個(gè)思想，我們考慮：約束為數(shù)位是p的倍數(shù)的個(gè)數(shù)，其中p數(shù)輸入的，這和上面sum%10類似，但是dp[pos][sum]顯然已經(jīng)不行了，每次p可能都不一樣，為了強(qiáng)行把memset提到外面加狀態(tài)dp[pos][sum][p]，對于每個(gè)不同p分別保存對應(yīng)的狀態(tài)。這里前提就比較簡單了，你dp數(shù)組必須合法，p太大就G_G了。所以對于與輸入有關(guān)的約束都可以強(qiáng)行增加狀態(tài)(這并不代表能ac，如果題目數(shù)據(jù)少的話就隨便你亂搞了)
第二：相減。
例題：HDU 4734
題目給了個(gè)f(x)的定義：F(x) = An
- 2n-1
- An-1
- 2n-2
- ... + A2
- 2 + A1
- 1，Ai是十進(jìn)制數(shù)位，然后給出a,b求區(qū)間[0,b]內(nèi)滿足f(i)<=f(a)的i的個(gè)數(shù)。
常規(guī)想：這個(gè)f(x)計(jì)算就和數(shù)位計(jì)算是一樣的，就是加了權(quán)值，所以dp[pos][sum]，這狀態(tài)是基本的。a是題目給定的，f(a)是變化的不過f(a)最大好像是4600的樣子。如果要memset優(yōu)化就要加一維存f(a)的不同取值，那就是dp[10][4600][4600]，這顯然不合法。
這個(gè)時(shí)候就要用減法了，dp[pos][sum]，sum不是存當(dāng)前枚舉的數(shù)的前綴和(加權(quán)的)，而是枚舉到當(dāng)前pos位，后面還需要湊sum的權(quán)值和的個(gè)數(shù)，
也就是說初始的是時(shí)候sum是f(a),枚舉一位就減去這一位在計(jì)算f(i)的權(quán)值，那么最后枚舉完所有位 sum>=0時(shí)就是滿足的，后面的位數(shù)湊足sum位就可以了。
仔細(xì)想想這個(gè)狀態(tài)是與f(a)無關(guān)的(新手似乎很難理解)，一個(gè)狀態(tài)只有在sum>=0時(shí)才滿足，如果我們按常規(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
這題的約束就是一個(gè)數(shù)的二進(jìn)制中0的數(shù)量要不能少于1的數(shù)量，通過上一題，這題狀態(tài)就很簡單了，dp[pos][num],到當(dāng)前數(shù)位pos,0的數(shù)量減去1的數(shù)量為num的方案數(shù)，一個(gè)簡單的問題，中間某個(gè)pos位上num可能為負(fù)數(shù)(這不一定是非法的，因?yàn)槲疫€沒枚舉完嘛，只要最終的num>=0才能判合法，中途某個(gè)pos就不一定了)，這里比較好處理，Hash嘛，最小就-32吧(好像),直接加上32，把32當(dāng)0用。這題主要是要想講一下lead的用法，顯然我要統(tǒng)計(jì)0的數(shù)量，前導(dǎo)零是有影響的。至于!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]);//有前導(dǎo)零就不統(tǒng)計(jì)在內(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 這題講一下：
（偷偷告訴你，這個(gè)oj是單組測試，然后memset什么的都是浮云了）
*約束：一個(gè)數(shù)是它自己數(shù)位和的倍數(shù)，直接dp根本找不到狀態(tài)，枚舉數(shù)位和，因?yàn)榭偩?62,然后問題就變成了一個(gè)數(shù)%mod=0，mod是枚舉的，想想狀態(tài)：dp[pos][sum][val]，當(dāng)前pos位上數(shù)位和是sum,val就是在算這個(gè)數(shù)%mod,（從高位算 10+i），因?yàn)槲覀兠杜e的數(shù)要保證數(shù)位和等于mod，還要保證這個(gè)數(shù)是mod的倍數(shù)，很自然就能找到這些狀態(tài)，顯然對于每一個(gè)mod，val不能保證狀態(tài)唯一，這是你要是想加一維dp[pos][sum][val][mod],記錄每一個(gè)mod的狀態(tài)(這里sum可以用減法，然而val不行，就只能加一維)，那你就想太多了，這樣是會超時(shí)的(因?yàn)闋顟B(tài)太多，記憶化效果不好)。這里直接對每一個(gè)mod，memset一次就能ac。下面的代碼還把limit的當(dāng)做了狀態(tài)，因?yàn)槊看味家跏蓟阅苓@樣，memset在多組外面是不能這樣的，不過奇葩的，這代碼，如果不把limit當(dāng)狀態(tài)，還是在!limit 條件下記錄dp，提交一發(fā)，時(shí)間竟然更短了，可能是每次memset的關(guān)系?。。?/em>
#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都不能達(dá)到0那就直接GG，這個(gè)剪枝不會影響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
*/
基本講的差不多了。前段時(shí)間學(xué)了點(diǎn)新東西！！
新的領(lǐng)域--計(jì)數(shù)轉(zhuǎn)求和
HDU 4507
這題麻煩就是要求數(shù)的平方和。
我們先考慮求和的問題，一個(gè)區(qū)間，數(shù)位dp能在一些約束下計(jì)數(shù)，現(xiàn)在要這些數(shù)的和。其實(shí)組合數(shù)學(xué)搞搞就可以了：如 現(xiàn)在枚舉的某一位pos,我統(tǒng)計(jì)了這一位枚舉i的滿足條件的個(gè)數(shù)cnt，其實(shí)只要算i對總和的貢獻(xiàn)就可以了，對于一個(gè)數(shù)而言第pos位是i，那么對求和貢獻(xiàn)就是i10^pos,就是十進(jìn)制的權(quán)值，然后有cnt個(gè)數(shù)都滿足第pos位是i，最后sum=cnti10^pos.原理就是這樣平方和可以看做(a10pos+b)2,a是你當(dāng)前pos位要枚舉的，b其實(shí)是個(gè)子問題，就是pos之后的位的貢獻(xiàn)值，把這個(gè)平方展開就可以了！
#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;//計(jì)數(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;
}
做題去~~
