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
",++kase,solve(y)-solve(x-1));
    }
    return 0;
}

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

Notes

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