HDU 4389 X mod f(x) (数位DP）

X mod f(x)

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1014 Accepted Submission(s): 453

Problem Description

Here is a function f(x): 　　　int f ( int x ) { 　　　    if ( x == 0 ) return 0; 　　　    return f ( x / 10 ) + x % 10; 　　　}

　　　Now, you want to know, in a given interval [A, B] (1 <= A <= B <= 10⁹), how many integer x that mod f(x) equal to 0.

Input

　　　The first line has an integer T (1 <= T <= 50), indicate the number of test cases. 　　　Each test case has two integers A, B.

Output

　　　For each test case, output only one line containing the case number and an integer indicated the number of x.

Sample Input

2

1 10

11 20

Sample Output

Case 1: 10

Case 2: 3

Author

WHU

Source

2012 Multi-University Training Contest 9

Recommend

zhuyuanchen520

题目大意：

def f(x):
int f ( int x ) {
　 if ( x == 0 ) return 0;
　 return f ( x / 10 ) + x % 10;
}

给出这么个函数，求[L, R]之间有多少个x满足x % f(x) == 0的

分析：

首先，这题的区间范围比较大，直接枚举必然TLE。（至于那种打表暴力搞过去的就不说，反正我个人是从来没这种水过去的命..T_T）

然后一个很明显的想法就是用部分合的思想,ans = gao(R) - gao(L-1),这是一个常用的做法，关键就在于如何设计这个gao()函数了

通常这种题常用的做法就是数位统计DP（当时青椒讲数位统计的时候没好好研究，悲催的搞了我好久）

经常观察可知f(x) <= 81, 设dp[len][mod][sum][res]表示长度为len，%mod, 和为sum, 余数为res的个数

根据同余定理，从后面填一个数字x，可得到状态转移方程 dp[len+1][mod][sum+x][(res*10 + x) % mod] += dp[len][mod][sum][res]

预处理的部分其实很简单，难点在于如何利用这个DP值统计[1...X] 的个数

从高位开始统计，假如当前位为第i位，当前位的数字为a_i, mod, 剩下数字和为s, 那么我们可取的数字j为0 ~ a_i - 1, 则枚举剩下可能的余数res

if num + j * 10^(i-1) + res % mod == 0 则把dp[i-1][mod][s - j][res] 加到ans里面，然后剩下最低位的时候单独处理一下就是了。

#include<stdio.h>
#include<string.h>

const int N=83;

int f[12][N][N][N];
int ten[15];

void Init(){
    int sum,res,mod,k;
    ten[0]=1;
    for(int i=1;i<=10;i++)
        ten[i]=ten[i-1]*10;
    memset(f,0,sizeof(f));
    for(int i=0;i<10;i++)
        for(int j=1;j<N;j++)
            f[1][i][j][i%j]=1;
    for(int i=1;i<9;i++)
        for(sum=0;sum<N;sum++)
            for(mod=0;mod<N;mod++)
                for(res=0;res<N;res++){
                    if(!f[i][sum][mod][res])
                        continue;
                    for(k=0;k<10 && sum+k<N;k++)
                        f[i+1][sum+k][mod][(res*10+k)%mod]+=f[i][sum][mod][res];
                }
}

int a[15];

int Do(int x){
    if(x<=10)
        return x;
    int tsum=0,tmp,len=0;
    for(tmp=x;tmp>0;tmp/=10)
        a[++len]=tmp%10,tsum+=tmp%10;

    int mod,sum,num,res,ans=0;
    for(mod=1;mod<=9*len;mod++){    //枚举取模，也就是所有数位的和
        if(mod>x)
            break;
        sum=mod;
        num=0;
        for(int i=len;i>1;i--){
            for(int j=0;j<a[i] && j<=sum;j++)       //从0...(a_i - 1)枚举。第i位的数
                for(res=0;res<mod;res++)            //res 表示i位以后的数位和取模得到的值
                    if((num+j*ten[i-1]+res)%mod==0)     //根据同余公式
                        ans+=f[i-1][sum-j][mod][res];
            sum-=a[i];
            num+=a[i]*ten[i-1];
        }
    }
    while(1){       //单独处理最低位
        if(x%tsum==0)
            ans++;
        if(x%10==0)
            break;
        x--;tsum--;
    }
    return ans;
}

int main(){

    //freopen("input.txt","r",stdin);

    Init();
    int t,a,b,cases=0;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&a,&b);
        printf("Case %d: %d\n",++cases,Do(b)-Do(a-1));
    }
    return 0;
}