视频网站费用,怎样建设简单的网站,开发工具idea简介,建设通官网首页Acwing 1084. 数字游戏 II
题意#xff1a;
指定一个整数闭区间 [a.b]#xff0c;问这个区间内有多少个取模数。 取模数#xff1a;这种数字必须满足各位数字之和 mod N 为 0。
题解#xff1a;
数位dp 这里不细讲数位dp了#xff0c;可以看看 Acwing 1081. 度的数量
指定一个整数闭区间 [a.b]问这个区间内有多少个取模数。 取模数这种数字必须满足各位数字之和 mod N 为 0。
题解
数位dp 这里不细讲数位dp了可以看看 Acwing 1081. 度的数量以及本人对数位dp的浅薄理解 Acwing 1082. 数字游戏 这里光讲讲本题与数位dp模板不同的地方 本题要求是的是各位数之和mod N为0 在预处理树的左侧部分时我们设dp[i][sum][j]:表示长度为i,最高位为j的各位之和%N等于sum 所以sum相当于是一个取模后的值 在求的过程中last表示之前各位数之和我们想要(lastsum)%N0,sum为第i位之后(含第i位)的各位数之和
(lastsum) mod n 0
sum (-last) mod n
sum mod(-last,n)mod为我定义的取模的函数因为会有负数取模所以不能直接用% 那么得到summod(-last,n) 直接加上该情况的f[i1][sum][j]即可
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn15;
int f[maxn][110][maxn];
int a,b,N;
int mod(int x,int y){return (x%yy)%y;
}
void init(){memset(f,0,sizeof(f));for(int i0;i9;i)f[1][i%N][i];//f[i][sum][j]:对于i位数最高位是j所有位数的和%n等于sum for(int i2;imaxn;i)for(int sum0;sumN;sum)for(int j0;j9;j)for(int k0;k9;k)f[i][sum][j]f[i-1][mod(sum-j,N)][k];
}
int solve(int n){if(!n)return 1;//0 mod n 0,所以0也是答案 int res0;int last0;//之前所有数的和 vectorintvec;while(n)vec.push_back(n%10),n/10;for(int ivec.size()-1;i0;i--){int xvec[i];for(int j0;jx;j){//(lastsum) mod n 0// sum (-last) mod n//sum mod(-last,n)resf[i1][mod(-last,N)][j];}lastx;//加上当前的上限走当前树节点的右侧部分 if(!ilast%N0)res;}return res;
}
int main()
{while(cinabN){init(); coutsolve(b)-solve(a-1)endl;}return 0;
}
