2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 J Beautiful Numbers (数位DP)

链接：https://ac.nowcoder.com/acm/contest/163/J?&headNav=acm来源：牛客网

时间限制：C/C++ 8秒，其他语言16秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

NIBGNAUK is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if it is divisible by the sum of its digits.

We will not argue with this and just count the quantity of beautiful numbers from 1 to N.

输入描述:

The first line of the input is T(1≤ T ≤ 100), which stands for the number of test cases you need to solve.Each test case contains a line with a positive integer N (1 ≤ N ≤ 1012).

输出描述:

For each test case, print the case number and the quantity of beautiful numbers in [1, N].

示例1

输入

[复制](javascript:void(0)😉

2
10
18

输出

[复制](javascript:void(0)😉

Case 1: 10
Case 2: 12

思路：

数位dp，

用dfs+记忆化来实现。

状态定义为\(dp[mod][pos][sum][remain]\) 代表各位到第pos位，数字的和为sum，对当前的数字对mod取余后为remain，目标是对mod取余为0的满足条件的个数。

也可以这样定义\(dp[pos][sum][remain]\)，少开一维，但是没对一个mod算答案时要对dp数组进行memset清空，

这样会只是多了20倍以上的常数。还是建议开四维来记录。

其他的就是正常的数位DP的套路。

当前的和为sum,remain为当前数的大小，由同余模定理可以知道，在计算中间取模与最后取模是一样的，所以可以每一步对remain取模。

代码：（177ms）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {a %= MOD; if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}

inline void getInt(int *p);
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
ll dp[120][13][120][120];
ll n;
ll num[40];
int id = 0;
int mod;

ll dfs(int pos, int sum, int rm, int limit)
{
    if (pos == 0) {
        return sum == mod && rm == 0;
    } else {
        if (!limit && dp[mod][pos][sum][rm] != -1) {
            return dp[mod][pos][sum][rm];
        }
        ll res = 0ll;
        int up = limit ? num[pos] : 9;
        for (int i = 0; i <= up; ++i) {
            if (sum + i > mod || sum + i + 9 * pos < mod) {
                break;
            }
            res += dfs(pos - 1, sum + i, (rm * 10 + i) % mod, limit && i == num[pos]);
        }
        if (!limit) {
            dp[mod][pos][sum][rm] = res;
        }
        return res;
    }
}
ll solve(ll x)
{
    id = 0;
    while (x) {
        num[++id] = x % 10;
        x /= 10;
    }
    ll res = 0ll;
    for (int i = 1; i <= id * 9; ++i) {
        mod = i;
        res += dfs(id, 0, 0, 1);
    }
    return res;
}
int main()
{
    //freopen("D:\\code\\text\\input.txt","r",stdin);
    //freopen("D:\\code\\text\\output.txt","w",stdout);
    int t;
    memset(dp, -1, sizeof(dp));
    scanf("%d", &t);
    for (int cas = 1; cas <= t; ++cas) {
        scanf("%lld", &n);
        printf("Case %d: %lld\n", cas, solve(n));
    }

    return 0;
}

inline void getInt(int *p)
{
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    } else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}