HDU 4389 X mod f(x) 数位dp

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4389

X mod f(x)

Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)

问题描述

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 <= 109), how many integer x that mod f(x) equal to 0.

输入

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

输出

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

样例输入

2
1 10
11 20

样例输出

Case 1: 10
Case 2: 3

题意

问区间[l,r]之间满足x%f[x]==0的x有多少个，其中f[x]表示x各数位之和。

题解

这题关键的地方是你如果把f[x]这个变量固定下来，那问题就变成普通的求模问题了。

dp[len][mod][k][r]表示f[x]=mod的那些数，前len位的各位数之和为k的，且取模mod的个数有多少个。

代码

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf

typedef int LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0);

//start----------------------------------------------------------------------

const int maxn=11;
const int maxm=82;

int arr[maxn],tot;
LL dp[maxn][maxm][maxm][maxm];
///ismax标记表示前驱是否是边界值
int _mod;
LL dfs(int len,int k, int mod, bool ismax) {
    if(k<0) return 0;
    if (len == 0) {
        ///递归边界
        if(k==0&&mod==0) return 1;
        return 0;
    }
    if (!ismax&&dp[len][_mod][k][mod]>=0) return dp[len][_mod][k][mod];

    LL res = 0;
    int ed = ismax ? arr[len] : 9;
    ///这里插入递推公式
    for (int i = 0; i <= ed; i++) {
        res += dfs(len - 1, k-i, (mod*10+i)%_mod,ismax&&i == ed);
    }

    return ismax ? res : dp[len][_mod][k][mod] = res;
}

LL solve(LL x) {
    tot = 0;
    while (x) { arr[++tot] = x % 10; x /= 10; }

    LL ret=0;
    for(int i=1;i<maxm;i++){
        _mod=i;
        LL res=dfs(tot,i,0,true);
        ret+=res;
    }

    return ret;
}

int main() {
    clr(dp,-1);
    int tc,kase=0;
    scf("%d",&tc);
    while(tc--){
        LL x,y;
        scf("%d%d",&x,&y);
        prf("Case %d: %d\n",++kase,solve(y)-solve(x-1));
    }
    return 0;
}

//end-----------------------------------------------------------------------

Notes

dp的状态的维数就是吧一些变量变成常量（去枚举变量），然后简化问题。所以做这类问题的时候可以考虑先把所有的变量都找出来，然后去分析。