[kuangbin带你飞]专题十五 数位DP

		ID	Origin	Title
	62 / 175	Problem A	CodeForces 55D	Beautiful numbers
	30 / 84	Problem B	HDU 4352	XHXJ's LIS
	108 / 195	Problem C	HDU 2089	不要62
	89 / 222	Problem D	HDU 3555	Bomb
	59 / 107	Problem E	POJ 3252	Round Numbers
	47 / 75	Problem F	HDU 3709	Balanced Number
	64 / 95	Problem G	HDU 3652	B-number
	42 / 124	Problem H	HDU 4734	F(x)
	11 / 20	Problem I	ZOJ 3494	BCD Code
	31 / 100	Problem J	HDU 4507	吉哥系列故事――恨7不成妻
	42 / 75	Problem K	SPOJ BALNUM	Balanced Numbers

62 / 175 Problem A CodeForces 55D Beautiful numbers

一个美丽数就是可以被它的每一位的数字整除的数。

给定一个区间，求美丽数的个数。

这题是很好的数位DP。

比较难想状态。

就是被每一个数字的LCM整除。

1~9的LCM最大是2520，其实也只有48个。

然后dp[i][j][k]表示处理到数位i,该数对2520取模为j,各个数位的LCM为k

/*
 * 题意：求区间[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 <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN=;
const int MOD=;//1~9的lcm为2520
long long dp[MAXN][MOD][];
int index[MOD+];//记录1~9的最小公倍数
int bit[MAXN];
int gcd(int a,int b)
{
    if(b==)return a;
    else return gcd(b,a%b);
}
int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}

void init()
{
    int num=;
    for(int i=;i<=MOD;i++)
        if(MOD%i==)
            index[i]=num++;
}
long long dfs(int pos,int preSum,int preLcm,bool flag)
{
    if(pos==-)
        return preSum%preLcm==;
    if(!flag && dp[pos][preSum][index[preLcm]]!=-)
        return dp[pos][preSum][index[preLcm]];
    long long ans=;
    int end=flag?bit[pos]:;//上界
    for(int i=;i<=end;i++)
    {
        int nowSum=(preSum*+i)%MOD;
        int nowLcm=preLcm;
        if(i)nowLcm=lcm(nowLcm,i);
        ans+=dfs(pos-,nowSum,nowLcm,flag && i==end);
    }
    if(!flag)dp[pos][preSum][index[preLcm]]=ans;
    return ans;
}
long long calc(long long x)
{
    int pos=;
    while(x)
    {
        bit[pos++]=x%;
        x/=;
    }
    return dfs(pos-,,,);
}
int main()
{
    int T;
    long long l,r;
    init();
    memset(dp,-,sizeof(dp));
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d%I64d",&l,&r);
        printf("%I64d\n",calc(r)-calc(l-));
    }
    return ;
}

30 / 84 Problem B HDU 4352 XHXJ's LIS

108 / 195 Problem C HDU 2089 不要62

d.求n~m间的数中，多少不带4和62的数。

n、m（0<n≤m<1000000）

s.见注释

#include<iostream>
#include<stdio.h>
using namespace std;

long long dp[][];
/*
i位数时，相应情况的数字总数
dp[i][0]，不含有不吉利数字
dp[i][1]，不含有不吉利数字，最高位为2
dp[i][2]，含有不吉利数字
*/
void init(){
    dp[][]=;
    dp[][]=dp[][]=;
    int i;
    for(i=;i<=;++i){
        dp[i][]=*dp[i-][]-dp[i-][];//不含不吉利数字前面加除4外9个数，减掉2前面加6
        dp[i][]=dp[i-][];//不含不吉利数字前面加2
        dp[i][]=*dp[i-][]+dp[i-][]+dp[i-][];//含不吉利数字前面加0~9，加上不含不吉利数字前加4，加上2前面加6
    }
}
int bit[];
int calc(int n){
    int len=,i,tmp=n;
    while(n){
        bit[++len]=n%;
        n/=;
    }
    bit[len+]=;
    bool flag=false;//前缀出现4或者62了吗
    long long ans=;
    for(i=len;i>=;--i){
        ans+=dp[i-][]*bit[i];//注意这个位置，求的是前缀+当前位置（0~bit[i]-1正好是bit[i]种，当前位是不能为bit[i]的）
        if(flag)ans+=dp[i-][]*bit[i];//此时当前位为0~bit[i]-1时，后面不含不吉利数字的全都不行
        else{//有3种情况
            if(bit[i]>)ans+=dp[i-][];//这位为4的时候（ps：为什么不是>=4？因为只有>4时才能保证当前位取4时，后面的数全都能取到，下同）
            if(bit[i+]==&&bit[i]>)ans+=dp[i][];//上位为6，这位为2的时候
            if(bit[i]>)ans+=dp[i-][];//这位为6的时候
        }
        if(bit[i]==||bit[i+]==&&bit[i]==)flag=true;//前缀出现的4或者62了。
    }
    if(flag)++ans;//加上n本身，这个数也不行
    return tmp-ans;
}

int main(){
    init();
    int n,m;

    while(scanf("%d%d",&n,&m)){
        if(n==&&m==)break;
        printf("%d\n",calc(m)-calc(n-));
    }
    return ;
}

89 / 222 Problem D HDU 3555 Bomb

d.求1到n有多少个数中含有49，1<=n<=2^63-1（2^32是10位，2^64约20位）

s.数位dp，和上个题类似，少了个条件

dp[i][0]，长度为i，不含有49的个数
dp[i][1]，长度为i，不含有49，最高位为9的个数
dp[i][2]，长度为i，含有49的个数

状态转移方程：

dp[i][0]=10*dp[i-1][0]-dp[i-1][1];//不含49的前面加0~9，减掉9前面加4
dp[i][1]=dp[i-1][0];//不含49的前面加9
dp[i][2]=10*dp[i-1][2]+dp[i-1][1];//含49的前面加0~9，加上9前面加4

求解：从最高位开始遍历，每一位求的都是  前缀+小于当前位  的符合条件的个数。

1.首先加上当前位置之后包含49的个数，因为当前为可以填0~bit[i]-1，所以乘以bit[i]，ans+=dp[i-1][2]*bit[i];//注意这个位置，求的是前缀+当前位置
2.前面的前缀出现49了，ans+=dp[i-1][0]*bit[i];//
3.前缀没有出现49，并且当前位>4，ans+=dp[i-1][1];

#include<iostream>
#include<stdio.h>
using namespace std;

long long dp[][];
/*
dp[i][0]，不含有49
dp[i][1]，不含有49，最高位为9
dp[i][2]，含有49
*/
void init(){
    dp[][]=;
    dp[][]=dp[][]=;
    int i;
    for(i=;i<;++i){
        dp[i][]=*dp[i-][]-dp[i-][];//不含49的前面加0~9，减掉9前面加4
        dp[i][]=dp[i-][];//不含49的前面加9
        dp[i][]=*dp[i-][]+dp[i-][];//含49的前面加0~9，加上9前面加4
    }
}
int bit[];
long long calc(long long n){
    int len=,i;
    while(n){
        bit[++len]=n%;
        n/=;
    }
    bit[len+]=;
    bool flag=false;
    long long ans=;
    for(i=len;i>=;--i){
        ans+=dp[i-][]*bit[i];//注意这个位置，求的是前缀+当前位置
        if(flag)ans+=dp[i-][]*bit[i];
        else if(bit[i]>)ans+=dp[i-][];
        if(bit[i+]==&&bit[i]==)flag=true;
    }
    if(flag)++ans;//加上n本身
    return ans;
}

int main(){
    init();
    int t;
    long long n;
    scanf("%d",&t);
    while(t--){
        scanf("%lld",&n);
        printf("%I64d\n",calc(n));
    }
    return ;
}

59 / 107 Problem E POJ 3252 Round Numbers

d.Round Numbers 就是一个表示成二进制的时候0比1多或者相等的正数，注意是正数，所以0就肯定不是了。
题目是给定一个区间，问在这个区间上的Round Numbers有多少个？
首先是求出小于等于n的Round Numbers有多少个。
s.我先举个例子来先说明，再来说一般方法。
比如： 22 = 10110b 如果要求 <=22的Round Numbers，也就是找出1-22有多少个二进制的0不少于1的数的个数。
22的二进制长度是5.
首先找长度比5小的Round Numbers（长度比5小的数肯定小于22啦）
长度为4的话，第一位必须是1，后面三位的话，可以有2个0，3个0
所以就是C(3,2)+C(3,3);
长度为3的Round Numbers，同理有 C(2,2);//注意不要把第一位1忘记了
长度为2的Round Numbers，有 C(1,1)
长度为1的Round Numbers，有 0个
下面是找长度和22相同的Round Numbers。
首先第一位是1.
22的第二位是0，所以第二位不能为1，必须是0
第三位为0的话，（前面有了2个0，1个1），后面两位可以有1个0，2个0
C（2，1）+C（2，2）
接下来把第三位恢复为1，看第四位。假如第四位是0，（前面有2个0，2个1），后面一位必须是0 C（1，1）
所以大致求的过程就如上面所述。

首先先推个公式，就是长度为len的Round Numbers的个数。
长度为len,第一位肯定是1了。
那么后面剩下 len-1位。
如果len-1是偶数。
那么 C（len-1,(len-1)/2+1)+C（len-1,(len-1)/2+2)+````C(len-1,len-1)
= ( 2^(len-1)-C(len-1,(len-1)/2) )/2;
如果len是奇数
那么就是 ( 2^(len-1) )/2
所以上面求比N长度小的Round Numbers是很好求的了。
至于求长度的，则是逐渐把每一位1变为0，去求后面的，就可以保证比n小了。
看代码吧。很容易理解的。

#include<iostream>
#include<stdio.h>
using namespace std;

int C[][];
void init(){
    C[][]=;
    C[][]=;C[][]=;
    int i,j;
    for(i=;i<;++i){
        C[i][]=;
        for(j=;j<i;++j){
            C[i][j]=C[i-][j-]+C[i-][j];
        }
        C[i][i]=;
    }
}
int bits[];
int calc(int n){////求小于等于n的 Round Numbers
    if(n==){//
        return ;
    }
    int len;
    len=;
    while(n>){
        if(n&){
            bits[len++]=;
        }
        else{
            bits[len++]=;
        }
        n>>=;
    }
    int ans;
    ans=;
    int i;
    //求出长度1~len-1的所有情况
    for(i=len-;i>;--i){
        if(i&){
            ans=ans+((<<(i-))-C[i-][(i-)/])/;
        }
        else{
            ans=ans+(<<(i-))/;
        }
    }
    int cnt0,cnt1;//前缀出现0的个数和1的个数
    cnt0=;
    cnt1=;
    int j;
    //长度为len的情况，小于n的
    for(i=len-;i>=;--i){
        if(bits[i]==){//后面有i位，当前第i位当成0
            for(j=i;j>=&&cnt0++j>=cnt1+i-j;--j){//后面i位中选j个0
                ans=ans+C[i][j];
            }
            ++cnt1;
        }
        else{
            ++cnt0;
        }
    }
    //看看原来这个数n
    cnt0=;
    cnt1=;
    for(i=;i<len;++i){
        if(bits[i]==){
            ++cnt0;
        }
        else{
            ++cnt1;
        }
    }
    if(cnt0>=cnt1){
        ++ans;
    }
    return ans;
}

int main(){
    init();
    int a,b;

    while(~scanf("%d%d",&a,&b)){
        printf("%d\n",calc(b)-calc(a-));
    }

    return ;
}

47 / 75 Problem F HDU 3709 Balanced Number

找出区间内平衡数的个数，所谓的平衡数，就是以这个数字的某一位为支点，另外两边的数字大小乘以力矩之和相等，即为平衡数

/*
 * HDU 3709
 * 平衡数，枚举支点
 * dp[i][j][k] i表示处理到的数位，j是支点，k是力矩和
 */

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
long long dp[][][];
int bit[];
long long dfs(int pos,int center,int pre,bool flag)
{
    if(pos==-)return pre==;
    if(pre<)return ;//当前力矩为负，剪枝
    if(!flag&&dp[pos][center][pre]!=-)
        return dp[pos][center][pre];
    int end=flag?bit[pos]:;
    long long ans=;
    for(int i=;i<=end;i++)
        ans+=dfs(pos-,center,pre+i*(pos-center),flag&&i==end);
    if(!flag)dp[pos][center][pre]=ans;
    return ans;
}
long long calc(long long n)
{
    int len=;
    while(n)
    {
        bit[len++]=n%;
        n/=;
    }
    long long ans=;
    for(int i=;i<len;i++)
        ans+=dfs(len-,i,,);
    return ans-(len-);//去掉全0的情况
}
int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int T;
    long long x,y;
    memset(dp,-,sizeof(dp));//这个初始化一定别忘记
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d%I64d",&x,&y);
        printf("%I64d\n",calc(y)-calc(x-));
    }
    return ;
}

64 / 95 Problem G HDU 3652 B-number

找出1~n范围内含有13并且能被13整除的数字的个数

/*
 * 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[][][][];
int bit[];
int dfs(int pos,int num,bool t,int e,bool flag)
{
    if(pos==-)return t&&(num==);
    if(!flag && dp[pos][num][t][e]!=-)
        return dp[pos][num][t][e];
    int end=flag?bit[pos]:;
    int ans=;
    for(int i=;i<=end;i++)
        ans+=dfs(pos-,(num*+i)%,t||(e==&&i==),i,flag&&(i==end));
    if(!flag)dp[pos][num][t][e]=ans;
    return ans;
}
int calc(int n)
{
    int pos=;
    while(n)
    {
        bit[pos++]=n%;
        n/=;
    }
    return dfs(pos-,,,,);
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    memset(dp,-,sizeof(dp));
    while(scanf("%d",&n)==)
    {
        printf("%d\n",calc(n));
    }
    return ;
}

42 / 124 Problem H HDU 4734 F(x)

定义十进制数x的权值为f(x) = a(n)*2^(n-1)+a(n-1)*2(n-2)+...a(2)*2+a(1)*1，a(i)表示十进制数x中第i位的数字。

题目给出a，b，求出0~b有多少个权值不大于f(a)的数。

dp[i][j]表示i位值<=j 的总数

/* ***********************************************
Author        :kuangbin
Created Time  :2013/9/14 星期六 12:45:42
File Name     :2013成都网络赛\1007.cpp
************************************************ */

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

int dp[][];

int bit[];

int dfs(int pos,int num,bool flag)
{
    if(pos == -)return num >= ;
    if(num < )return ;
    if(!flag && dp[pos][num] != -)
        return dp[pos][num];
    int ans = ;
    int end = flag?bit[pos]:;
    for(int i = ;i <= end;i++)
    {

        ans += dfs(pos-,num - i*(<<pos),flag && i==end);
    }
    if(!flag)dp[pos][num] = ans;
    return ans;
}

int F(int x)
{
    int ret = ;
    int len = ;
    while(x)
    {
        ret += (x%)*(<<len);
        len++;
        x /= ;
    }
    return ret;
}
int A,B;
int calc()
{
    int len = ;
    while(B)
    {
        bit[len++] = B%;
        B/=;
        //cout<<bit[len-1]<<endl;
    }
    //cout<<F(A)<<endl;
    return dfs(len-,F(A),);
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T;
    int iCase = ;
    scanf("%d",&T);
    memset(dp,-,sizeof(dp));
    while(T--)
    {
        iCase++;
        scanf("%d%d",&A,&B);
        printf("Case #%d: %d\n",iCase,calc());
    }
    return ;
}

11 / 20 Problem I ZOJ 3494 BCD Code
31 / 100 Problem J HDU 4507 吉哥系列故事――恨7不成妻

如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关——
　　1、整数中某一位是7；
　　2、整数的每一位加起来的和是7的整数倍；
　　3、这个整数是7的整数倍；

要求一个区间中和7无关的数的平方和。

需要用数位DP维护3个值：

1.与7无关的数的个数

2.与7无关的数的和

3、与7无关的数的平方和。

第一个是与7无关的数的个数，就是简单的数位DP了，很常规。

第二个与7无关的数的和的维护需要用到第一个个数。

处理到第pos个数位时，加上i*10^pos * 后面的个数

第三个的维护需要用到前面两个

(pre*10^pos + next)^2= (pre*10^pos)^2+2*pre*10^pos*next +next^2

/*
 * 　如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关——
　　1、整数中某一位是7；
　　2、整数的每一位加起来的和是7的整数倍；
　　3、这个整数是7的整数倍；

求一个区间中与7无关的数的平方和
 */
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const long long MOD=1000000007LL;
struct Node
{
    long long cnt;//与7无关的数的个数
    long long sum;//与7无关的数的和
    long long sqsum;//平方和
}dp[][][];//分别是处理的数位、数字和%7,数%7
int bit[];
long long p[];//p[i]=10^i

Node dfs(int pos,int pre1,int pre2,bool flag)
{
    if(pos==-)
    {
        Node tmp;
        tmp.cnt=(pre1!= && pre2!=);
        tmp.sum=tmp.sqsum=;
        return tmp;
    }
    if(!flag && dp[pos][pre1][pre2].cnt!=-)
        return dp[pos][pre1][pre2];
    int end=flag?bit[pos]:;
    Node ans;
    Node tmp;
    ans.cnt=ans.sqsum=ans.sum=;
    for(int i=;i<=end;i++)
    {
        if(i==)continue;
        tmp=dfs(pos-,(pre1+i)%,(pre2*+i)%,flag&&i==end);
        ans.cnt+=tmp.cnt;
        ans.cnt%=MOD;
        ans.sum+=(tmp.sum+ ((p[pos]*i)%MOD)*tmp.cnt%MOD )%MOD;
        ans.sum%=MOD;

        ans.sqsum+=(tmp.sqsum + ( (*p[pos]*i)%MOD )*tmp.sum)%MOD;
        ans.sqsum%=MOD;
        ans.sqsum+=( (tmp.cnt*p[pos])%MOD*p[pos]%MOD*i*i%MOD );
        ans.sqsum%=MOD;
    }
    if(!flag)dp[pos][pre1][pre2]=ans;
    return ans;
}
long long calc(long long n)
{
    int pos=;
    while(n)
    {
        bit[pos++]=n%;
        n/=;
    }
    return dfs(pos-,,,).sqsum;
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T;
    long long l,r;
    p[]=;
    for(int i=;i<;i++)
        p[i]=(p[i-]*)%MOD;
    for(int i=;i<;i++)
        for(int j=;j<;j++)
            for(int k=;k<;k++)
                dp[i][j][k].cnt=-;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d%I64d",&l,&r);
        long long ans=calc(r);
        ans-=calc(l-);
        ans=(ans%MOD+MOD)%MOD;
        printf("%I64d\n",ans);
    }
    return ;
}

42 / 75 Problem K SPOJ BALNUM Balanced Numbers

这题要求出现的数字，偶数出现奇数次，奇数出现偶数次。

用三进制表示0~9的状态

//============================================================================
// Name        : SPOJ.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long dp[][];
//3进制表示数字0~9的出现情况，0表示没有出现，1表示奇数次，2表示偶数次
int bit[];
bool check(int s)
{
    int num[];
    for(int i=;i<;i++)
    {
        num[i]=s%;
        s/=;
    }
    for(int i=;i<;i++)
        if(num[i]!=)
        {
            if(i%== && num[i]==)return false;
            if(i%== && num[i]==)return false;
        }
    return true;
}
int getnews(int x,int s)
{
    int num[];
    for(int i=;i<;i++)
    {
        num[i]=s%;
        s/=;
    }
    if(num[x]==)num[x]=;
    else num[x]=-num[x];
    int news=;
    for(int i=;i>=;i--)
    {
        news*=;
        news+=num[i];
    }
    return news;
}
long long dfs(int pos,int s,bool flag,bool z)
{
    if(pos==-)return check(s);
    if(!flag && dp[pos][s]!=-)
        return dp[pos][s];
    long long ans=;
    int end=flag?bit[pos]:;
    for(int i=;i<=end;i++)
        ans+=dfs(pos-,(z&&i==)?:getnews(i,s),flag&&i==end,z&&i==);
    if(!flag)dp[pos][s]=ans;
    return ans;
}
long long calc(long long n)
{
    int len=;
    while(n)
    {
        bit[len++]=n%;
        n/=;
    }
    return dfs(len-,,,);
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T;
    memset(dp,-,sizeof(dp));
    long long a,b;
    scanf("%d",&T);
    while(T--)
    {
        cin>>a>>b;
        cout<<calc(b)-calc(a-)<<endl;
    }
    return ;
}

ps：从这个题发现了pow的精度问题，呵呵

http://blog.csdn.net/u014665013/article/details/70990408