[UOJ #140]【UER #4】被粉碎的数字

客官°小女子只卖身不卖艺 2021-10-29 08:42 107阅读 0赞

**题目大意：**定义$f(x)$为数字$x$每一位数字的和，求$\\sum\\limits\_\{i=1\}^R\[f(x)=f(kx)\]$。$R\\leqslant10^\{18\},k\\leqslant10^3$

**题解：**数位$DP$，从低位到高位$DP$，定义$f\[i\]\[j\]\[x\]\[y\]$为从低到高第$i$位，$j=f(a\\bmod\{10^i\})-f(ka\\bmod\{10^i\})$，$ka\\equiv x\\pmod\{10^i\}$，$y=\[a>(R\\bmod\{10^i\})\]$，转移显然。注意到$ka$位数大于$a$导致$DP$不全，可以添加$R$的位数（因为$k\\leqslant10^3$，就添加$3$位）

**卡点：**无

**C++ Code：**

#include <cstdio>
    #include <iostream>
    #include <algorithm>
    
    int k, num[30], tot;
    long long f[30][500][1000][2], x;
    int main() {
    	std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    	std::cin >> x >> k;
    	while (x) num[++tot] = x % 10, x /= 10;
    	tot += 3;
    	f[0][250][0][0] = 1;
    	for (int i = 0; i < tot; ++i)
    		for (int j = -200; j <= 200; ++j)
    			for (int x = 0; x < 1000; ++x)
    				for (int y = 0; y < 2; ++y) if (f[i][j + 250][x][y]) {
    					for (int z = 0; z < 10; ++z)
    						f[i + 1][j + z - (k * z + x) % 10 + 250][(k * z + x) / 10][z == num[i + 1] ? y : z > num[i + 1]] += f[i][j + 250][x][y];
    				}
    	std::cout << f[tot][250][0][0] - 1 << '\n';
    	return 0;
    }

转载于:https://www.cnblogs.com/Memory-of-winter/p/11214658.html

发表评论取消回复

表情：

评论列表（有 0 条评论，107人围观）

还没有评论，来说两句吧...

相关阅读

相关 uoj#209【UER #6】票数统计

[题目][Link 1] 做UER的A题涨信心首先我们注意到这个所谓的至少有一条正确在\\(x\\)和\\(y\\)不相等的时候非常弱，当\\(x<y\\)时，只有可能是

小咪咪/ 2023年10月11日 11:20/ 0 赞/ 29 阅读

相关 uoj140 【UER #4】被粉碎的数字

[题目][Link 1] 看起来就像是数位\\(\\rm dp\\) 不妨从竖式乘法的角度来考虑这个问题为了方便处理进位，我们得从低位向高位填数设\\(dp\[i\

喜欢ヅ旅行/ 2023年10月11日 04:57/ 0 赞/ 16 阅读

相关 uoj139 【UER #4】被删除的黑白树

[题目][Link 1] 不难发现有一个暴力\\(dp\\) 设\\(dp\[x\]\[l\]\\)表示\\(x\\)点子树内所有叶子节点到\\(x\\)的路径上都有\\(

我不是女神ヾ/ 2023年10月11日 04:48/ 0 赞/ 9 阅读

相关（每日一练C++）CC140 回文数字

描述在不使用额外的内存空间的条件下判断一个整数是否是回文。回文指逆序和正序完全相同。数据范围：-2^\{31\} \\le n \\le 2^\{31\}-1−

小灰灰/ 2023年10月04日 17:56/ 0 赞/ 23 阅读

相关 UER（腾讯）

现存的预训练模型中没有一种可以完美的适用于所有任务，这也给预训练模型的选择带来困难。对于这个问题，论文提供了一种切实可行的解决方案，即UER（Universal Encoder

冷不防/ 2023年09月25日 12:39/ 0 赞/ 91 阅读

相关 UOJ安装指南

linux环境 Ubuntu 16.04 第一步 docker安装 apt-get安装的不一定是最新的docker，安装版本是1.10.2，不过，对于docker使用没

- 日理万妓/ 2022年06月04日 06:35/ 0 赞/ 466 阅读

相关 [uoj#246]套路

部分分$3:m<=1000$ 当$m>1000$时,必有两个跳蚤的值相同，所以只要枚举$m<=1000$的区间转载于:https://www.cnblogs.com/lx

末蓝、/ 2021年11月16日 23:22/ 0 赞/ 349 阅读

相关 [UOJ #140]【UER #4】被粉碎的数字

题目大意：定义$f(x)$为数字$x$每一位数字的和，求$\\sum\\limits\_\{i=1\}^R\[f(x)=f(kx)\]$。$R\\leqslant10^\{18

客官°小女子只卖身不卖艺/ 2021年10月29日 08:42/ 0 赞/ 108 阅读

相关【UOJ 456】括号匹配

【题目描述】：我们给出了“正则括号”序列的归纳定义：空序列是一个正则括号序列，如果S是一个正则括号序列，则（s）和\[s\]是正则括号序列，

淡淡的烟草味﹌/ 2021年10月26日 21:44/ 0 赞/ 296 阅读

相关 UOJ 12 猜数

[ 描述][Link 1] [ 提交][Link 2] [ 自定义测试][Link 3] 这一天，小Y、小D、小C正在愉快地玩耍。小Y是个数学家，他一拍

快来打我*/ 2021年09月29日 04:32/ 0 赞/ 295 阅读