AcWing 1084. 数字游戏 II(一种不一样的写法)
原题链接
中等
作者:
菜菜-胶胶
,
2022-07-27 20:44:24
,
所有人可见
,
阅读 160
一种不一样的写法,莫名奇妙就过了,我还得理解理解、、、
// #pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define int long long
using namespace std;
#ifdef Kenshin
#include "/Myfunc/debug.h"
#else
#define pr(...) cerr << "Accpect" << '\n'
#endif
#define sp ' '
#define endl '\n'
#define pb push_back
#define mod(x) ((x) % mod)
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> PII;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10;
int n, m, p;
int f[11][100];
void init(){
for(int i = 0; i <= 9; i ++) f[1][i % p] ++;
f[0][0] = 1;
for(int i = 2; i < 11; i ++)
for(int j = 0; j <= 9; j ++)
for(int k = 0; k < p; k ++)
f[i][(j + k) % p] += f[i - 1][k];
}
int dp(int n){
if(!n) return 1;
vector<int> nums;
while(n) nums.pb(n % 10), n /= 10;
int res = 0;
for(int i = nums.size() - 1; i >= 1; i --){
res += f[i][0];
if(i != 1) res -= f[i - 1][0];
}
// cout << "--------" << res << endl;
int last = 0;
for(int i = nums.size() - 1; i >= 0; i --){
int x = nums[i];
int start = i == nums.size() - 1;
for(int j = start; j < x; j ++)
res += f[i][(p - ((j + last) % p)) % p];
last = (last + x) % p;
if(!i && last == 0) res ++;
}
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int l, r;
while(cin >> l >> r >> p){
memset(f, 0, sizeof f);
init();
cout << dp(r) - dp(l - 1) << endl;
}
return 0;
}