数位dp总结

/*数位dp模板
int dfs(int i, int s, bool e) {
    if (i==-1) return s==target_s;
    if (!e && ~f[i][s]) return f[i][s];
    int res = 0;
    int u = e?num[i]:9;
    for (int d = first?1:0; d <= u; ++d)
        res += dfs(i-1, new_s(s, d), e&&d==u);
    return e?res:f[i][s]=res;
}
~~f为记忆化数组；

~~i为当前处理串的第i位（权重表示法，也即后面剩下i+1位待填数）；

~~s为之前数字的状态（如果要求后面的数满足什么状态，也可以再记一个目标状态t之类，for的时候枚举下t）；

~~e表示之前的数是否是上界的前缀（即后面的数能否任意填）。

~~for循环枚举数字时，要注意是否能枚举0，以及0对于状态的影响，有的题目前导0和中间的0是等价的，
  但有的不是，对于后者可以在dfs时再加一个状态变量z，表示前面是否全部是前导0，也可以看是否是首位，
  然后外面统计时候枚举一下位数。It depends.
*/
hdu2089（求区间不包含62和4的数的个数）
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[10][10];
void init()
{
    memset(dp,0,sizeof(dp));
    dp[0][0] = 1;
    for(int i=1;i<=7;i++)
    {
        for(int j=0;j<10;j++)
        {
            for(int k=0;k<10;k++)
            {
                if(j!=4&&!(j==6&&k==2))
                    dp[i][j]  += dp[i-1][k];
            }
        }
    }
}
int solve(int n)//找的范围是<n
{
    init();
    int digit[10];
    int len = 0;
    while(n>0)
    {
        digit[++len] = n%10;
        n/=10;
    }
    digit[len+1]=0;
    int ans = 0;
    for(int i=len;i;i--)
    {
        for(int j=0;j<digit[i];j++)
        {
            if(j!=4&&!(digit[i+1]==6&&j==2))
                ans+=dp[i][j];
        }
        if(digit[i]==4||(digit[i]==2&&digit[i+1]==6))
            break;
    }
    return  ans;
}
int main()
{
    int l,r;
    while(cin>>l>>r)
    {
        if(l+r==0)
            break;
        else
            cout<<solve(r+1)-solve(l)<<endl;    //由于要找[l,r],而solve函数找的范围为<n,所以传参的时候应该特别注意
    }
    return 0;

}
（模板解决）
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[10][2][11];
int bit[15];
int dfs(int pos,int have,int end,bool limit){
    if(pos==0)
        return !have;
    if(!limit&&dp[pos][have][end]!=-1)
        return dp[pos][have][end];
    long long ans=0;
    int num=limit?bit[pos]:9;
    for(int i=0;i<=num;i++){
         if((end==6&&i==2)||i==4)
             ans+=dfs(pos-1,1,i,limit&&i==num);
         else
             ans+=dfs(pos-1,have,i,limit&&i==num);


    }
    if(!limit)
        dp[pos][have][end]=ans;
    return ans;
}

int   cal(long long n){
    memset(dp,-1,sizeof(dp));
    memset(bit,0,sizeof(bit));
    int len=0;
    while(n){
        bit[++len]=n%10;
        n=n/10;
    }
    return dfs(len,0,0,true);
}
int main(){
 
         int l,r;
while(~        scanf("%d%d",&l,&r)){
    if(l==0&&r==0)
        break;
//        memset(dp,-1,sizeof(dp));
  int   ans=cal(r)-cal(l-1);
        printf("%d\n",ans);
    }
    return 0;
}



HDU3652(求[0,n]区间含子串13并且是13的倍数)
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[15][15][5];
//一维为位数，二维为余数，三维为目前的状态
int bit[15];
///have==0,,,,末尾不是1&&无13
///hava==1,,,,末尾是1  &&无13
///hava==2,,,,含有13
int dfs(int pos,int mod,int have,int limit){
      if(pos==0)
        return mod==0&&have==2;
      if(!limit&&dp[pos][mod][have]!=-1)
        return dp[pos][mod][have];
        int ans=0;
      int num=limit?bit[pos]:9;
      for(int i=0;i<=num;i++){
            int mod_t=(mod*10+i)%13;
            int have_x=have;
            if(have==0&&i==1)
                have_x=1;
            if(have==1&&i!=1)
                have_x=0;
            if(have==1&&i==3)
                have_x=2;
            ans+=dfs(pos-1,mod_t,have_x,limit&&i==num);

      }
      if(!limit)
        dp[pos][mod][have]=ans;
      return ans;
}

int main(){
   int n;
   while(scanf("%d",&n)!=EOF){
        int len=0;
        memset(dp,-1,sizeof(dp));
        memset(bit,0,sizeof(bit));
        while(n){
            bit[++len]=n%10;
            n=n/10;
        }
        int cnt=dfs(len,0,0,1);
        printf("%d\n",cnt);
   }
   return 0;
}
/*
 * HDU 3652 B-number(简单化)
 * 含有数字13和能够被13整除的数的个数
 * dp[i][j][k][z]：i:处理的数位，j:该数对13取模以后的值，k:是否已经包含13,z结尾的数
 */
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
int dp[12][15][2][10];
int bit[12];
int dfs(int pos,int num,bool t,int e,bool flag)
{
    if(pos==-1)return t&&(num==0);
    if(!flag && dp[pos][num][t][e]!=-1)
        return dp[pos][num][t][e];
    int end=flag?bit[pos]:9;
    int ans=0;
    for(int i=0;i<=end;i++)
        ans+=dfs(pos-1,(num*10+i)%13,t||(e==1&&i==3),i,flag&&(i==end));
    if(!flag)dp[pos][num][t][e]=ans;
    return ans;
}
int calc(int n)
{
    int pos=0;
    while(n)
    {
        bit[pos++]=n%10;
        n/=10;
    }
    return dfs(pos-1,0,0,0,1);
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    memset(dp,-1,sizeof(dp));
    while(scanf("%d",&n)==1)
    {
        printf("%d\n",calc(n));
    }
    return 0;
}

codeforce55d
/*
 * 题意：求区间[x , y]中beautiful number的个数，
 * a positive integer number is beautiful if and only
 * if it is divisible by each of its nonzero digits.
分析：一个数能被它的所有非零数位整除，则能被它们的最小公倍数整除，而1到9的最小公倍数为2520，
数位DP时我们只需保存前面那些位的最小公倍数就可进行状态转移，到边界时就把所有位的lcm求出了，
为了判断这个数能否被它的所有数位整除，我们还需要这个数的值，显然要记录值是不可能的，其实我们只
需记录它对2520的模即可，这样我们就可以设计出如下数位DP：dfs(pos,mod,lcm,f),pos为当前
位，mod为前面那些位对2520的模，lcm为前面那些数位的最小公倍数，f标记前面那些位是否达到上限，
这样一来dp数组就要开到19*2520*2520，明显超内存了，考虑到最小公倍数是离散的，1-2520中可能
是最小公倍数的其实只有48个，经过离散化处理后，dp数组的最后一维可以降到48，这样就不会超了。
 */
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=25;
const int mod=2520;
int bit[maxn];
long long dp[maxn][mod][48];
int index[mod+10];


void init(){
  int cnt=0;
  for(int i=1;i<=mod;i++){
    if(mod%i==0)
        index[i]=cnt++;
  }
}

int gcd(int a,int b){
   if(b==0)
       return a;
   else
   return gcd(b,a%b);
}

int lcm(int a,int b){
   return a/gcd(a,b)*b;
}

long long  dfs(int pos,int presum,int prelcm,bool limit){
      if(pos==0)
          return presum%prelcm==0;
      if(!limit&&dp[pos][presum][index[prelcm]]!=-1)
          return dp[pos][presum][index[prelcm]];
      long long ans=0;
      int num=limit?bit[pos]:9;
      for(int i=0;i<=num;i++){
           int nowsum=(presum*10+i)%mod;
           int nowlcm=prelcm;
           if(i){
              nowlcm=lcm(nowlcm,i);
           }
           ans+=dfs(pos-1,nowsum,nowlcm,limit&&i==num);
      }
      if(!limit)
          dp[pos][presum][index[prelcm]]=ans;
      return ans;

}


long long calc(long long n){
    memset(bit,0,sizeof(bit));
    int len=0;
    while(n){
         bit[++len]=n%10;
         n=n/10;
    }
    return dfs(len,0,1,true);
}
int main(){
    int t;
    init();
    memset(dp,-1,sizeof(dp));
    scanf("%d",&t);
    while(t--){
        long long l,r;
        scanf("%I64d%I64d",&l,&r);
        printf("%I64d\n",calc(r)-calc(l-1));
    }
    return 0;
}
POJ 3252Round Numbers
给定一个区间L,R
求这个区间里面每个数的二进制形式中0比1的数的总个数
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=35;
int dp[maxn][maxn][maxn];
int bit[maxn];
int dfs(int pos,int num0,int num1,bool first,bool limit ){
    if(pos==0)
    return num0>=num1;
    if(!limit&&dp[pos][num0][num1]!=-1)
    return dp[pos][num0][num1];
    int ans=0;
    int num=limit?bit[pos]:1;
    for(int i=0;i<=num;i++){
         if(first){
             if(i==0)
             ans+=dfs(pos-1,0,0,first,limit&&i==num);
             else
           ans+=  dfs(pos-1,num0,num1+1,false,limit&&i==num);
         }
        else{
            if(i==0)
            ans+=dfs(pos-1,num0+1,num1,false,limit&&i==num);
            else
            ans+=dfs(pos-1,num0,num1+1,false,limit&&i==num);
        }
    }
    if(!limit)
    dp[pos][num0][num1]=ans;
    return ans;
}
int cal(int n){
    int len=0;
    memset(dp,-1,sizeof(dp));
    memset(bit,0,sizeof(bit));
    while(n){
      bit[++len]=n&1;
        n>>=1;
    }
    return  dfs(len,0,0,1,1);
}


int main(){
   int l,r;
    while(scanf("%d%d",&l,&r)!=EOF){
        memset(dp,-1,sizeof(dp));
        int ans=cal(r)-cal(l-1);
        printf("%d\n",ans);
    }
    return 0;
}
HDU 3709    Balanced Number
求一个区间内的平衡数
对此题平衡数的定义为, 4139 is a balanced number with pivot fixed at 3. The torqueses are 4*2 + 1*1 = 9 and 9*1 = 9, for left part and right part, 
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int bit[20];
long long  dp[20][20][2000];

long long dfs(int pos,int point,int sum,bool limit){
     if(pos==0)
         return sum==0;
     if(sum<0)
         return 0;
     if(!limit&&dp[pos][point][sum]!=-1)
         return dp[pos][point][sum];
     long long ans=0;
     int num=limit?bit[pos]:9;
     for(int i=0;i<=num;i++){
         ans+=dfs(pos-1,point,i*(pos-point)+sum,limit&&i==num);
     }
     if(!limit)
         dp[pos][point][sum]=ans;
     return ans;
}

long long cal(long long n){
   memset(dp,-1,sizeof(dp));
   memset(bit,0,sizeof(bit));
   int len=0;
   while(n){
      bit[++len]=n%10;
      n=n/10;
   }
   long long sum=0;
   for(int i=1;i<=len;i++)
       sum+=dfs(len,i,0,true);
   return sum-len+1;
}


int main(){
  int t;
  scanf("%d",&t);
  while(t--){
     long long l,r;
     scanf("%lld%lld",&l,&r);
     long long  ans=cal(r)-cal(l-1);
     printf("%lld\n",ans);
  }
  return 0;
}
hdu4507   F(x)
For a decimal number x with n digits (A nA n-1A n-2 ... A 2A 1), we define its weight as F(x) = A n * 2 n-1 + A n-1 * 2 n-2 + ... + A 2 * 2 + A 1 * 1. Now you are given two numbers A and B, please calculate how many numbers are there between 0 and B, inclusive, whose weight is no more than F(A).
Sample Input
3
0 100
1 10
5 100 
Sample Output
Case #1: 1
Case #2: 2
Case #3: 13 
输入A,B
求在区间【0，b】内f（x）的值不大于a的值得数量
dp[i][j]表示i位数中权值不大于j的数量
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[20][200000];
int bit[20];
//int a,b;
int dfs(int pos,int sum,bool limit){
       if(pos==0)
           return sum>=0;
       if(sum<0)
           return 0;
        if(!limit&&dp[pos][sum]!=-1)
            return dp[pos][sum];
        int res=0;
        int end=limit?bit[pos]:9;
        for(int i=0;i<=end;i++){
           res+=dfs(pos-1,sum-i*(1<<(pos-1)),limit&&i==end);
        }
        if(!limit)
            dp[pos][sum]=res;
        return res;

}

int f(int a){
    int len=0;
    int res=0;
    while(a){
        res+=(a%10)*(1<<len);
        len++;
        a=a/10;
    }
    return res;
}
int a,b;
int cal(){
     int len=0;
     while(b){
         bit[++len]=b%10;
         b=b/10;
     }
     return dfs(len,f(a),true);

}

int main(){
    int t;
    scanf("%d",&t);
    int cas=0;
      memset(dp,-1,sizeof(dp));
    while(t--){
        cas++;
      
    //    memset(bit,0,sizeof(bit));
        scanf("%d%d",&a,&b);
        int ans=cal();
       printf("Case #%d: %d\n",cas,ans);
    }
    return 0;
}