Morikka's Blog

猫里卡的部落格

• Algorithm

数位 DP 小结

概述

一般是求小于等于数字N的某些特征数字个数，或者是区间[L,R]的之间的某些特征数字个数，后者一般可以转换成求差的方式来做。

模板

数字处理函数：

int f(int num){
    int ans;
    int pos = 0;
    while(num){
        digit[++pos]=num%10;
        num=num/10;
    }
    return dfs( pos, s , true );
}
其中：

digit为处理串的每个数位的数值。 s为初始的状态。 如果有其他限定条件，dfs 中可以增加参数。

DFS函数：

int dfs(int l, int s, bool jud) {
    if ( l==-1 ) return s == target_s;
    if ( !e && ~f[l][s] ) return f[l][s];
    int ans = 0;
    int nex = e ? digit[i] : 9;
    for (int d = 0; d <=  nex; ++d)
        ans += dfs( l-1 , new_s( s,d ) , e && d==nex );
    return jud ? ans : f[l][s] = ans;
}
其中：

f为记忆化数组； l为当前处理串的第l位（权重表示法，也即后面剩下l+1位待填数）； s为之前数字的状态（如果要求后面的数满足什么状态，也可以再记一个目标状态t之类，for的时候枚举下t）； jud表示之前的数是否是上界的前缀（即后面的数能否任意填）。 for循环枚举数字时，要注意是否能枚举0，以及0对于状态的影响，有的题目前导0和中间的0是等价的，但有的不是，对于后者可以在dfs时再加一个状态变量z，表示前面是否全部是前导0，也可以看是否是首位，然后外面统计时候枚举一下位数。It depends. 于是关键就在怎么设计状态。当然做多了之后状态一眼就可以瞄出来。

前导零的判断：
int dfs(bool zero)
......
ans+=dfs(zero&&i==0)//不区分前导零与零
ans+=dfs(zero&&i==0&&l>1)//区分前导零与零

题目：

A. 【CF55D】

#####题意： 给定区间[L,R]，求区间完美数字的个数。（一个数字是完美数字当且仅当该数字可整除其所有数位上的非零数）

思路：

位数上的数字只需要考虑2~9，因此用一个数字1<<8来表示有哪些数字出现过。 如果一个数是所有位数的倍数，那么一定是其最小公倍数的倍数，其所有的最小公倍数是2520，所以求和的时候直接对2520取余。 dp[l][cnt][sum]，l为数字长度，cnt为位数上有哪些数，sum为数字和。 dfs(int l, int cnt, int sum, bool jud)，jud为是否为边界。

代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
int digit[20];
LL dp[20][(1<<8)][2520];
LL dfs(int l,int cnt,int sum,bool jud){
    if(l==0){
        for(int i=2;i<=9;i++)
            if( (cnt&(1<<(i-2))) && (sum%i) ){
                return 0;
            }
        return 1;
    }
    if(!jud && dp[l][cnt][sum] != -1) return dp[l][cnt][sum];
    int nes = jud ? digit[l] : 9;
    LL pos = 0 ;
    for(int i=0;i<=nes;i++){
        pos += dfs(l-1 , i<2 ? cnt : (cnt|(1<<(i-2))) , ((sum*10)+i)%2520 , jud&&(i==digit[l]));
    }
    if(!jud)
        dp[l][cnt][sum]=pos;
    return pos;
}
LL f(LL k){
    LL ans;
    int pos = 0;
    while(k){
        digit[++pos]=k%10;
        k=k/10;
    }
    ans = dfs(pos,0,0,true);
    return ans;
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    memset(dp,-1,sizeof(dp));
    int t;
    LL m,n;
    cin>>t;
    while(t--){
        cin>>m>>n;
        cout<<f(n)-f(m-1)<<endl;
    }
return 0;
}

B. 【HDU4352】

题意：

寻找[L,R]中间所有数字串中LIS（最长上升子序列）为K的数字和。

思路：

LIS运用动态规划可以在O(nlogn)的时间复杂度解决，此略。 因为最多只有0～9十个数字，因此可以预处理。 sta为LIS的状态，siz[sta]中保存LIS的长度（即二进制中1的个数），nex[sta][l]为在sta中插入数字l之后的LIS状态。 dp[l][sta][k]：l为数字长度，sta为当前LIS的状态，k为所要求的LIS长度。 dfs(int l, int sta, bool zero, bool jud)：zero判断是否为前导零，jud为是否为边界。 注意：dp[l][sta][k]中，k并不是必须的，然而因为本题样例组数过多且k很小，所以选择增加一维表状态而不是每次都初始化以节约时间。

代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
int digit[20],siz[1<<10],nex[1<<10][10];
LL dp[66][(1<<10)][11];
int Cas,k;
LL dfs(int l,int sta,bool zero,bool jud){
    if(l==0) return siz[sta]==k;
    if(!jud&&dp[l][sta][k]!=-1)return dp[l][sta][k];
    int nes = jud ? digit[l] : 9;
    LL ans = 0;
    for(int i=0;i<=nes;i++)
        ans+= dfs(l-1, (zero&&i==0) ? 0 : nex[sta][i] , zero&&i==0 , jud&&i==nes);
    if(!jud)dp[l][sta][k]=ans;
    return ans;
}
LL f(LL num){
    int pos = 0;
    while(num){
        digit[++pos]=num%10;
        num/=10;
    }
    return dfs(pos,0,true,true);
}
int find_nex(int status,int num){
    for(int i=num;i<10;i++)
        if (status&(1<<i)) return (status^(1<<i)|(1<<num));
    return status|(1<<num);
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<(1<<10);i++){
        siz[i]=0;
        for(int j=0;j<10;j++){
            if(i&(1<<j))siz[i]++;
            nex[i][j]=find_nex(i,j);
        }
    }
    int t;
    LL m,n;
    cin>>t;
    while(t--){
        cin>>m>>n>>k;
        cout<<"Case #"<<++Cas<<": ";
        cout<<f(n)-f(m-1)<<endl;
    }
return 0;
}

C. 【HDU2089】

题意：

[L,R]中，不含4或62的数字个数。

思路：

dp[l][six]：l为数字长度，six为最后一位数字是否为6。 dfs(int l,bool six,bool jud)，jud判断是否为边界。

代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int digit[10],dp[10][2],vis[10][2];
int dfs(int l,bool six,bool jud){
    if(l==0) return 1;
    if(!jud&&vis[l][six])return dp[l][six];
    int len = jud ? digit[l] : 9;
    int nes = 0;
    for(int i=0;i<=len;i++){
        if((i==4)||(six&&i==2)) continue;
    nes += dfs(l-1 , i==6 , jud&&(i==len));
    }
    if(!jud){
        vis[l][six]=true;
        dp[l][six]=nes;
    }
    return nes;
}
int f(int k){
    memset(dp,0,sizeof(dp));
    memset(vis,0,sizeof(vis));
    int pos = 0;
    while(k){
        digit[++pos]=k%10;
        k=k/10;
    }
    int ans = dfs(pos,false,true);
    return ans;
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
int m,n;
    while(scanf("%d%d",&m,&n)&&(m+n)){
        cout<<f(n)-f(m-1)<<endl;
    }
return 0;
}

D. 【HDU3555】

题意：

数字中含有49的数字个数。

思路：

偷了下懒，用C题的代码求不含49的个数，然后做差，居然过了= =b。其实这道题打表都行= =b。

代码：
#include <cstring>
#include <cstdio>
#include <iostream>
#define LL long long
using namespace std;
int digit[25];
LL dp[25][2];
LL dfs(int l,bool num,bool jud){
    if(l==0) return 1;
    if(!jud && dp[l][num]!=-1) return dp[l][num];
    LL ans=0;
    int nex = jud ? digit[l] : 9;
    for(int i=0;i<=nex;i++){
        if(num&&i==9)continue;
        ans += dfs(l-1,i==4,jud&&i==nex);
    }
    if(!jud) dp[l][num]=ans;
    return ans;
}
LL f(LL num){
    int pos = 0;
    while(num){
        digit[++pos]=num%10;
        num/=10;
    }
    return dfs(pos,false,true);
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int T;
    LL n;
    memset(dp,-1,sizeof(dp));
    scanf("%d",&T);
    while(T--){
        cin>>n;
        cout<<n-f(n)+1<<endl;
    }
    return 0;
}

E. 【HDU3252】

题意：

数字[L,R]中，round number数字的个数。round number即数字转换成二进制后0的个数大于等于1的个数。

思路：

digit数组中直接保存该数字的二进制形式。 dp[l][cnt1][cnt2][zero]：l为数字长度，cnt1为数字0的数字个数，cnt2为数字1的数字个数，zero判断是否为前导零。 dfs(int l,int cnt1,int cnt2,bool zero,bool jud)：jud判断是否为边界。

代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int digit[35],dp[35][35][35][2],pos;
int dfs(int l,int cnt1,int cnt2,bool zero,bool jud){
    if(l==0) return cnt1>=cnt2;
    if(!jud&&dp[l][cnt1][cnt2][zero]!=-1) return dp[l][cnt1][cnt2][zero];
    int nex = jud ? digit[l] : 1;
    int ans = 0;
    for(int i=0;i <= nex;i++){
        ans += dfs( l-1 , zero ? 0 : cnt1+(i==0) ,cnt2+(i==1) , zero&&(i==0) , jud&&i==nex );
    }
    if(!jud)dp[l][cnt1][cnt2][zero]=ans;
    return ans;
}
int f(int num){
    pos = 0;
    while(num){
        digit[++pos]=num%2;
        num>>=1;
    }
    return dfs(pos,0,0,true,true);
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    memset(dp,-1,sizeof(dp));
    int m,n;
    cin>>m>>n;
    cout<<f(n)-f(m-1)<<endl;
    return 0;
}

F. 【HDU3709】

题意：

统计区间[L,R]中，balanced number的数字个数。balanced number即对于任意一个数字串，假设其有一个数字位，它左边的数字乘距离的和等于它右边的数字乘距离的和，则其为balanced number。

思路：

枚举作为平衡点的数字位数，最后要减掉（pos-1）因为对于0,计算了0,00,000…重复计算了pos次，只需要保留一次。 dp[l][o][pos]：长度为l，平衡点位置为o时的当前状态（pos为0时表示平衡，pos>0则为左边的沉，pos<0则为右边的沉） dfs(int l,int o,int pos,bool jud)：jud判断是否为边界。 注意只要pos<0就可以返回false。

代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define LL long long
int digit[20];
LL dp[20][20][2000];
LL dfs(int l,int o,int pos,bool jud){
    if( l==0 ) return pos == 0;
    if( pos<0 ) return 0;
    if(!jud && dp[l][o][pos] >= 0)return dp[l][o][pos];
    int nex = jud ? digit[l] : 9;
    LL ans = 0;
    for(int i=0;i<=nex;i++)
        ans += dfs( l-1 , o , pos+i*(l-o) , jud && i==nex );
    return jud ? ans : dp[l][o][pos] = ans;
}
LL f(LL num){
    int pos = 0;
    while(num){
        digit[++pos]=num%10;
        num/=10;
    }
    LL ans = 0;
    for(int i=1;i<=pos;i++)
        ans += dfs(pos,i,0,true);
    ans = ans - pos + 1;
    return ans;
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    memset(dp,-1,sizeof(dp));
    int T;
    LL m,n;
    cin>>T;
    while(T--){
        cin>>m>>n;
        cout<<f(n)-f(m-1)<<endl;
    }
    return 0;
}

G. 【HDU3652】

题意：

[1,n]的含数字13且为13的倍数的数字个数。

思路：

dp[l][mod][iso][has]：l为数字长度，mod为当前数字对13的取余值，iso为是否存在，has为最后一位是否为数字1。 int dfs(int l,int mod,bool iso,bool has,bool jud)：jud判断是否为边界值。

代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int digit[11];
int dp[11][13][2][2];
int dfs(int l,int mod,bool iso,bool has,bool jud){
    if(l==0)return (has && !mod);
    if(!jud && dp[l][mod][iso][has])return dp[l][mod][iso][has];
    int nex = jud ? digit[l] : 9;
    int ans = 0;
    for(int i=0;i<=nex;i++){
        ans += dfs( l-1 , (mod*10+i)%13 , i==1 , has||(iso&&i==3) , jud && i==nex );
    }
    return jud ? ans : dp[l][mod][iso][has]=ans;
}
int f(int num){
    int pos = 0;
    while(num){
        digit[++pos]=num%10;
        num/=10;
    }
    return dfs(pos,0,false,false,true);
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int n;
    while(~scanf("%d",&n)){
        printf("%d\n",f(n));
    }
    return 0;
}

H. 【HDU4734】

题意：

对于每个数字x，都有一个F（x）值，让你求[0,B]中，函数值小于等于F（A）的数字个数。

思路：

首先计算出F（a）。 dp[l][sum]：l为当前数字长度，sum为F（A）减去之前枚举的数字的数字差（如果差为正则代表F（A）大）。 dfs(int l,int sum,bool jud)：jud判断是否为边界。

代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int digit[10],dp[10][100005],CASE;
int dfs(int l,int sum,bool jud){
    if( l==0 ) return sum >= 0;
    if( sum<0 )return 0;
    if( !jud && dp[l][sum]>=0 ) return dp[l][sum];
    int nex = jud ? digit[l] : 9;
    int ans = 0;
    for(int i=0 ; i<=nex ; i++)
        ans += dfs( l-1 , sum-i*(1<<(l-1)) , jud&&i==nex );
    return jud ? ans : dp[l][sum] = ans;
}
inline int f(int num,int cas){
    int pos = 0;
    while(num){
        digit[++pos]=num%10;
        num/=10;
    }
    return dfs(pos,cas,true);
}
inline int count(int a){
    int pos = 0,ans = 0;
    while(a){
        ans+=(a%10)*(1<<pos++);
        a/=10;
    }
    return ans;
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    memset(dp,-1,sizeof(dp));
    int T,a,b,cas;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&a,&b);
        cas = count(a);
        //cout<<">"<<cas<<endl;
        printf("Case #%d: ",++CASE);
        printf("%d\n",f(b,cas));
    }
    return 0;
}

I. 【ZOJ3494】

题意：

区间[L，R]的数字转换成BCD之后，不含有forbidden code（即长度不超过20的01组成的数字串）的数字个数。

思路：

forbidden code可以用trie树储存。 dp[l][pos]：l为数字长度，pos为树上的位置。 dfs(int l,int pos,bool zero,bool jud)：zero判断是否为前导零（注意和数字0区分），jud判断是否为边界。

代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int M = 10005,MOD=1000000009;
#define LL long long

int idx;
char str[25];
int bcd[2005][10];
LL dp[205][2005];
int digit[205],len,n;

struct Trie{
    Trie *next[2];
    Trie *fail;
    int isword,kind;
};
Trie *que[M],s[M];

Trie *NewNode(){
    Trie *tmp=&s[idx];
    tmp->next[0]=tmp->next[1]=NULL;
    tmp->isword=0;
    tmp->fail=NULL;
    tmp->kind=idx++;
    return tmp;
}
void Insert(Trie *root,char *s,int l){
    Trie *p=root;
    for(int i=0; i<l; i++){
        if(p->next[s[i]-'0']==NULL) p->next[s[i]-'0']=NewNode();
        p=p->next[s[i]-'0'];
    }
    p->isword=1;
}
void Bulid_fail(Trie *root){
    int head=0,tail=0;
    que[tail++]=root;
    root->fail=NULL;
    while(head<tail){
        Trie *tmp=que[head++];
        for(int i=0; i<2; i++){
            if(tmp->next[i]){
                if(tmp==root) tmp->next[i]->fail=root;
                else{
                    Trie *p=tmp->fail;
                    while(p!=NULL){
                        if(p->next[i]){
                            tmp->next[i]->fail=p->next[i];
                            break;
                        }
                        p=p->fail;
                    }
                    if(p==NULL) tmp->next[i]->fail=root;
                }
                if(tmp->next[i]->fail->isword)
                    tmp->next[i]->isword=tmp->next[i]->fail->isword;
                que[tail++]=tmp->next[i];
            }
            else if(tmp==root) tmp->next[i]=root;
            else tmp->next[i]=tmp->fail->next[i];
        }
    }
}
//状态当前在状态pre,经过一个数字num之后到达哪个状态
//如果不合法，返回-1
int BCD(int pre,int num){
    if(s[pre].isword) return -1;
    int cur=pre;
    for(int i=3;i>=0;i--){
        int k=(num>>i)&1;
        if(s[cur].next[k]->isword) return -1;
        else cur=s[cur].next[k]->kind;
    }
    return cur;
}
void Get_next(){
    for(int i=0;i<idx;i++){
        for(int j=0;j<10;j++){
            bcd[i][j]=BCD(i,j);
        }
    }
}
LL dfs(int l,int pos,bool zero,bool jud){
    if(pos<0) return 0;
    if(l==0)return 1;
    if(!jud&&dp[l][pos]>=0)return dp[l][pos];
    LL ans = 0;
    int nex = jud ? digit[l] : 9;
    for(int i=0;i<=nex;i++)
        ans += dfs( l-1 , zero&&i==0&&l>1 ? pos : bcd[pos][i] , zero&&i==0 , jud&&i==nex );
    ans%=MOD;
    return jud ? ans : dp[l][pos]=ans;
}
LL cal(char *s,int l){
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=l;i++) digit[l-i+1]=s[i-1]-'0';
    dfs(l,0,true,true);
}
char A[205],B[205];

void sub(char *s,int len){
    for(int i=len-1;i>=0;i--){
        if(s[i]=='0') s[i]='9';
        else{
            s[i]--;
            break;
        }
    }
}

int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    while(t--){
        idx=0;
        Trie *root=NewNode();
        scanf("%d",&n);
        for(int i=1; i<=n; i++){
            scanf("%s",str);
            Insert(root,str,strlen(str));
        }
        Bulid_fail(root);
        Get_next();
        scanf("%s",A);
        sub(A,strlen(A));
        scanf("%s",B);
        cout<<((cal(B,strlen(B))-cal(A,strlen(A)))%MOD+MOD)%MOD<<endl;
    }
    return 0;
}

J. 【HDU4507】

题意：

区间[L,R]中，和7无关的数字的平方和是多少？含7的数、数位和为7的倍数、数为7的倍数都是和7有关的数字。

思路：

dp[len][sum][remain]：len为长度，sum为数位和，remain为前缀和。 dfs(int len,int sum,int remain,bool jud)jud判断是否为边界。 维护三个数字：个数，和，平方和。 a[1]^2 + a[2]^2 + … + a[n]^2，新式是 (a[1]+b)^2 + (a[2]+b)^2 + … + (a[n]+b)^2，按照这样的原理求前缀的平方和。

代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
typedef pair< int,pair<LL,LL> > PILL;//< count , < sum，square sum> >
#define F first
#define S second
#define MP make_pair
const int mod = 1e9+7, mx = 20;
int digit[mx];
LL pow10[20];
PILL dp[20][7][7];
bool vis[20][7][7];
//边界的答案不同
PILL dfs(int len,int sum,int remain,bool jud){
    if(!len)
        if(sum&&remain)
            return MP(1,MP(0LL,0LL));
        else
            return MP(0,MP(0LL,0LL));
    if(!jud&&vis[len][sum][remain])
            return dp[len][sum][remain];
    PILL res = MP(0,MP(0LL,0LL));
    int nex = jud ? digit[len] : 9;
    for(int i=0;i<=nex;i++){
        if(i==7) continue;
        PILL ans = dfs(len-1,(sum+i)%7,(remain*10+i)%7,jud&&i==nex);
        LL pref = i * pow10[len-1] % mod;
        res.F += ans.F;
        res.F %= mod;
        res.S.F += ans.S.F + pref * ans.F;
        res.S.F %= mod;
        res.S.S += ans.S.S + pref * pref % mod * ans.F + 2 * pref * ans.S.F;
        res.S.S %= mod;
    }
    if(!jud){
        vis[len][sum][remain]=true;
        dp[len][sum][remain]=res;
    }
    return res;
}
LL f(LL a){
    memset(vis,0,sizeof(vis));
    int len=0;
    while(a){
        digit[++len]=a%10;
        a=a/10;
    }
    return dfs(len,0,0,true).S.S;
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    pow10[0]=1;
    for(int i=1;i<20;i++)
        pow10[i]=pow10[i-1]*10%mod;
    int t;
    scanf("%d",&t);
    while(t--){
        LL a,b,ans;
        scanf("%lld%lld",&a,&b);
        ans = (f(b)-f(a-1)+mod)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}

K. 【SPOJ10606】

题意：

求[L,R]中positive integer的数字个数。positive integer就是对于一个数字串，偶数数字各有奇数个，奇数数字各有偶数个。

思路：

用一个三进制数字表示每个数字的状态，0为未出现过，1为出现过奇数次，2为出现过偶数次。 dp[l][s]：l为数字长度，s为当前所有数字出现的状态。 dfs(int l,int s,bool zero,bool jud)：zero判断是否为前导零，jud判断是否为边界。

代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define LL long long
int dp[20][60000];
int digit[20];
LL pos[11];
void init(){
    pos[0]=1;
    for(int i=1;i<=10;i++)
        pos[i]=pos[i-1]*3;
}
bool judge(int s){
    for(int i=9;i>=0;i--){
        if(i%2==0 && s/pos[i]==2) return false;
        if(i%2==1 && s/pos[i]==1) return false;
        s%=pos[i];
    }
    return true;
}
LL dfs(int l,int s,bool zero,bool jud){
    if(l==0){
        if(judge(s))
            return 1;
        return 0;
    }
    if(!jud && dp[l][s]>=0)return dp[l][s];
    int nes = jud ? digit[l] : 9;
    LL ans = 0;
    for(int i=0;i<=nes;i++)
        ans += dfs(l-1 , zero&&i==0 ? 0 : ((s%pos[i+1])/pos[i]==2 ? s-pos[i] : s+pos[i]), zero&&i==0 , jud&&i==nes);
    return jud ? ans : dp[l][s] = ans;
}
LL f(LL num){
   int pos=0;
    while(num){
        digit[++pos]=num%10;
        num/=10;
    }
    return dfs(pos,0,true,true);
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    init();
    int T;
    LL a,b;
    cin>>T;
    memset(dp,-1,sizeof(dp));
    while(T--){
        cin>>a>>b;
        cout<<f(b)-f(a-1)<<endl;
    }
    return 0;
}

参考资料

刘聪《浅谈数位类统计问题》

高逸涵《数位计数问题解法研究》

http://www.cnblogs.com/jffifa/archive/2012/08/17/2644847.html

http://blog.csdn.net/dslovemz/article/details/8540340

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70324#overview

以及各种搜题解是搜到的blog= =b

最近的文章

powerset & set-o-gram

两个经典的对于集合的可视化展示方案，分别是 powerset 和 set-o-gram。…

• Research继续阅读
更早的文章

树状数组——题目集

整理了一些树状数组的题目，从易到难。…

• Algorithm继续阅读