# AcWing 1084. 数字游戏 II(AcWing 1084. Digital game II)-其他

## AcWing 1084. 数字游戏 II(AcWing 1084. Digital game II)

``````#include <bits/stdc++.h>

using namespace std;

const int N = 15;
const int M = 110; //mod N=0 N=100

int l, r, n;
int a[N];
int dp[N][M];

int dfs(int pos, int sum, bool limit) {
if (pos == -1) return !(sum % n);
if (!limit && ~dp[pos][sum]) return dp[pos][sum];
int res = 0, up = limit ? a[pos] : 9;
for (int i = 0; i <= up; i++)
res += dfs(pos - 1, sum + i, limit && i == a[pos]);
return limit ? res : dp[pos][sum] = res;
}

int calc(int x) {
memset(dp, -1, sizeof dp);
int pos = 0;
while (x) a[pos++] = x % 10, x /= 10;
return dfs(pos - 1, 0, true);
}

int main() {
while (cin >> l >> r >> n)
cout << calc(r) - calc(l - 1) << endl;
return 0;
}

``````
————————

Title portal

``````#include <bits/stdc++.h>

using namespace std;

const int N = 15;
const int M = 110; //mod N=0 N=100

int l, r, n;
int a[N];
int dp[N][M];

int dfs(int pos, int sum, bool limit) {
if (pos == -1) return !(sum % n);
if (!limit && ~dp[pos][sum]) return dp[pos][sum];
int res = 0, up = limit ? a[pos] : 9;
for (int i = 0; i <= up; i++)
res += dfs(pos - 1, sum + i, limit && i == a[pos]);
return limit ? res : dp[pos][sum] = res;
}

int calc(int x) {
memset(dp, -1, sizeof dp);
int pos = 0;
while (x) a[pos++] = x % 10, x /= 10;
return dfs(pos - 1, 0, true);
}

int main() {
while (cin >> l >> r >> n)
cout << calc(r) - calc(l - 1) << endl;
return 0;
}

``````