首页 > 其他分享 >SP8177 JZPEXT - Beautiful numbers EXTREME 题解

SP8177 JZPEXT - Beautiful numbers EXTREME 题解

时间:2024-07-02 19:09:50浏览次数:19  
标签:Beautiful 2520 题解 ll SP8177 len 数码 lcm operatorname

题目传送门

前置知识

数位 DP | 同余

解法

同余的传递性:若 \(\begin{cases} a,b \in \mathbf{Z} \\ p,q \in \mathbb{N}^{*} \\ q|p \end{cases}\) ,则当 \(a \equiv b \pmod{p}\) 时有 \(a \equiv b \pmod{q}\)。故在本题中 \(\bmod\) 各非零数码均等于 \(0\) 等价于 \(\bmod\) 各非零数码的 \(\operatorname{lcm}\) 等于 \(0\),等价于 \(\mod 2520\) 后的结果 \(\bmod\) 各非零数码的 \(\operatorname{lcm}\) 等于 \(0\)。

同时,对于 \(S \subset \{1,2,3,4,5,6,7,8,9 \}\),有 \(\operatorname{lcm}\limits_{x \in S} \{ x \}|2520\)。

所以我们可以预处理出 \(2520\) 的因数并离散化,分别记录当前位置、所构成的数字 \(\mod 2520\) 后的结果、非零数码的 \(\operatorname{lcm}\), 接着就和正常的数位 DP 一样了。

注意搜索顺序对答案继承的影响。

另外,本题限制代码长度 \(<1kB\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n'
ll a[25],g[2600],f[25][2600][55];
ll lcm(ll a,ll b)
{
	return a/__gcd(a,b)*b;
}
ll divide(ll n,ll a[])
{
	ll len=0;
	while(n)
	{
		len++;
		a[len]=n%10;
		n/=10;
	}
	return len;
}
ll dfs(ll pos,ll pre_sum,ll pre_lcm,ll limit,ll p)
{
	if(pos<=0)
	{
		return (pre_sum%pre_lcm==0);
	}
	if(f[pos][pre_sum][g[pre_lcm]]!=-1&&limit==0)
	{
		return f[pos][pre_sum][g[pre_lcm]];
	}
	ll ans=0,maxx=(limit==0)?9:a[pos],i;
	for(i=0;i<=maxx;i++)
	{
		ans+=dfs(pos-1,(pre_sum*10%p+i)%p,(i==0)?pre_lcm:lcm(pre_lcm,i),(i==maxx)*limit,p);
	}
	return (limit==0)?f[pos][pre_sum][g[pre_lcm]]=ans:ans;
}
ll ask(ll n)
{
	ll len=divide(n,a);
	return dfs(len,0,1,1,2520);
}
void init()
{
	ll num=0;
	memset(f,-1,sizeof(f));
	for(ll i=1;i<=2520;i++)
	{
		if(2520%i==0)
		{
			num++;
			g[i]=num;
		}
	}
}
int main()
{
	ll t,l,r,i;
	cin>>t;
	init();
	for(i=1;i<=t;i++)
	{
		cin>>l>>r;
		cout<<ask(r)-ask(l-1)<<endl;
	}
	return 0;
}

后记

多倍经验: CF55D Beautiful numbers

标签:Beautiful,2520,题解,ll,SP8177,len,数码,lcm,operatorname
From: https://www.cnblogs.com/The-Shadow-Dragon/p/18280392

相关文章

  • P5324 题解
    题意给定一个数列\(\{a_n\}\),定义一次删除操作为:假设当前序列长度为\(len\),删除序列中所有等于\(len\)的数。现在有\(m\)个操作,每次操作为单点修改或整体加减。每次操作完后,你需要修改若干个数,使得序列能够在若干次删除操作后被删空,求最小修改次数。数据范围:\(1\len,m......
  • 复旦大学2023--2024学年第二学期(23级)高等代数II期末考试第七大题解答
    七、(10分) 设$V$是$n$阶实矩阵全体构成的实线性空间, $A$是$n$阶正定实对称阵.对任意的$X,Y\inV$,定义二元函数$(X,Y)=\mathrm{tr}(XAY')$.(1)求证:$(-,-)$是$V$上的一个内积.(2)在上述内积下,$V$成为一个欧氏空间. 设$P,Q\inV$,$V$上的线性算子$......
  • abc360 E 题解
     E对于位置2~n,它们的概率是相等的。n*n个(x,y)对。其中x可以等于y。 对于x/y,y的逆元rev(y)为mul(y,mod-2)。加、减、乘、除都可以做。比如48/9和16/3的结果是一样的,48*rev(9)%mod=16*rev(3)%mod。比如3*rev(2)%mod=(rev(2)+rev(2)+rev(2))%mod. 对于每次操作,有多少......
  • 十四、Redis应用问题解决
    文章目录一、缓存穿透1.1问题描述1.2解决方案二、缓存击穿2.1问题描述2.2解决方案三、缓存雪崩3.1问题描述3.2解决方案四、分布式锁4.1问题描述4.2解决方案:使用redis实现分布式锁4.3编写代码4.4优化之设置锁的过期时间4.5优化之UUID防误删4.6优化之LUA脚......
  • P10676 『STA - R6』b20 题解
    题目传送门简单题,主要考察字符串。首先输入一个char类型的数组,然后输入粉丝的数量,最后直接输出数组的第一个以及粉丝的数量即可。温馨提示:提交此题时请务必将数组开大,否则你可能会获得\(90\)分高分。//『STA-R6』b20//codeby:cq_irritater//time:2024/06/30#in......
  • 【秋招突围】2024届秋招笔试-科大讯飞笔试题-03-三语言题解(Java/Cpp/Python)
    ......
  • [JLU] 数据结构与算法上机题解思路分享-第二次上机
    前言首先,请务必自己尽全力尝试实现题目,直接看成品代码,思维就被拘束了,也很容易被查重。这里只是思路解析的博客,代码仓库在JLU_Data_Structures_Record希望你能在这里找到你想要的:)正文A二叉树的创建与遍历分数10作者朱允刚单位吉林大学通过带空指针信息的先根序列(......
  • Atcoder ABC 360 全题解
    致歉对不起,我不应该在全题解的编写上咕咕咕两个月,导致流量大量流失。我知错了,下次还犯。AB无C考虑一个箱子里的所有球,我们需要把这些球放进互不相同的一些箱子里。然而我们可以留一个球在箱子里,显然留重量最大的最好,所以答案就是$\sum_{i=1}^{N}W_i$减去每个箱子里的最......
  • CF1987E 题解
    CF1987E题解题意给定一棵大小为\(n\)的有根树,各点各有一点权\(a_i\)。每次操作可以选定一节点使其点权加一,求最小的操作数,使得任一节点满足其点权不大于其所有儿子的点权之和。\(n\le5000,0\lea_i\le10^9\)题解麻了,赛后十五分钟调出来,可惜为时已晚。读懂题之后......
  • CF1375D Replace by MEX 题解
    题目大意令mexmexmex为序列中最小的没有出现的数。给你一个长度为......