刷题动态规划——数位DP数字游戏 2各位数字:和模N为0
这题可以包含前导0,因为前导0对各位数字之和没有影响。
先预处理出f[i, j, k]
,代表位数是i
,最高位是j
,被N
整除余k
的数的个数。
例如f[3, 6, 9]
就是600~699中被N整数余9的数的个数。
对于f[i, j, k]
,加上i-1位,最高位是l的余数符合要求的数f[i-1, l, t]
即可,其中 ( t j ) % n = k (t j)\%n=k (t j)%n=k。
换而言之 t = k p ∗ n − j t=k p*n-j t=k p∗n−j, p = 0 , 1 , 2 , . . . p=0,1,2,... p=0,1,2,...
之后同其他数位DP分析方式相同,先看最高位 a n − 1 a_{n-1} an−1,枚举最高位 j j j是 0 a n − 1 − 1 0~a_{n-1}-1 0 an−1−1的情况,将满足的数的个数加入答案,注意这边有 i 1 i 1 i 1位,答案要加 f [ i 1 ] [ j ] [ t ] f[i 1][j][t] f[i 1][j][t],接着更新 l a s t last last,看下一位。
l a s t last last用来记录前面几位的和,因此这边的 t t t满足 ( t l a s t ) % n = 0 (t last)\%n=0 (t last)%n=0。换而言之 t = p ∗ n − l a s t t=p*n-last t=p∗n−last, p = 0 , 1 , 2 , . . . p=0,1,2,... p=0,1,2,...
这题不看到最后一位尚不知道所有答案,因此不会提前break退出。
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 105;
const int M = 15; // 2^31 < 1e10
int a, b, n;
int f[M][M][N];
void init(int n) {
for (int j = 0; j <= 9; j ) {
f[1][j][j % n] ;
}
for (int i = 2; i < M; i ) {
for (int j = 0; j <= 9; j ) {
for (int k = 0; k < n; k ) {
for (int l = 0; l <= 9; l ) {
for (int p = 0; k p * n - j < n; p ) {
int t = k p * n - j;
if (t >= 0) f[i][j][k] = f[i - 1][l][t];
}
}
}
}
}
}
int dp(int num) {
if (!num) return 1;
vector<int> nums;
while(num) nums.push_back(num % 10), num /= 10;
int res = 0, last = 0;
for (int i = nums.size() - 1; i >= 0; i -- ) {
int x = nums[i];
for (int j = 0; j < x; j ) {
for (int k = 0; k * n - last < n; k ) {
int t = k * n - last;
if (t >= 0) res = f[i 1][j][t];
}
}
last = (last x) % n;
if (!i && !last) res ;
}
return res;
}
int main() {
while(~scanf("%d%d%d", &a, &b, &n)) {
memset(f, 0, sizeof f);
init(n);
printf("%d\n", dp(b) - dp(a - 1));
}
return 0;
}
由于上面初始化的 t t t满足 ( t j ) % n = k (t j)\%n=k (t j)%n=k,dp过程中的 t t t满足 ( t l a s t ) % n = 0 (t last)\%n=0 (t last)%n=0。由 f f f的定义,这边的 t t t也是 % n \%n %n的余数,范围在 [ 0 , n − 1 ] [0,n-1] [0,n−1],因此不必枚举 p p p,只需自定义取模的规则mod,使得mod结果都为正数即可。
int mod(int x, int y) {
return (x % y y) % y; // 所有模数返回正数
}
这样 ( t j ) % n = k (t j)\%n=k (t j)%n=k变成 t = m o d ( k − j , n ) t=mod(k-j, n) t=mod(k−j,n), ( t l a s t ) % n = 0 (t last)\%n=0 (t last)%n=0变成 t = m o d ( − l a s t , n ) t=mod(-last, n) t=mod(−last,n)
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 105;
const int M = 15; // 2^31 < 1e10
int a, b, n;
int f[M][M][N];
int mod(int x, int y) {
return (x % y y) % y; // 所有模数返回正数
}
void init(int n) {
for (int j = 0; j <= 9; j ) {
f[1][j][j % n] ;
}
for (int i = 2; i < M; i ) {
for (int j = 0; j <= 9; j ) {
for (int k = 0; k < n; k ) {
for (int l = 0; l <= 9; l ) {
f[i][j][k] = f[i - 1][l][mod(k - j, n)];
}
}
}
}
}
int dp(int num) {
if (!num) return 1;
vector<int> nums;
while(num) nums.push_back(num % 10), num /= 10;
int res = 0, last = 0;
for (int i = nums.size() - 1; i >= 0; i -- ) {
int x = nums[i];
for (int j = 0; j < x; j ) {
res = f[i 1][j][mod(-last, n)];
}
last = (last x) % n;
if (!i && !last) res ;
}
return res;
}
int main() {
while(~scanf("%d%d%d", &a, &b, &n)) {
memset(f, 0, sizeof f);
init(n);
printf("%d\n", dp(b) - dp(a - 1));
}
return 0;
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggbfgi
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01