首页 > 其他分享 >【题解】「NOIP2024模拟赛24 T3」钙绿

【题解】「NOIP2024模拟赛24 T3」钙绿

时间:2024-11-08 22:07:54浏览次数:1  
标签:24 10 le 题解 bmod 循环 NOIP2024

【题解】「NOIP2024模拟赛24 T3」钙绿

https://www.becoder.com.cn/contest/5715/problem/3


\(\mathcal{Description}\)

给定 \(n,p,m\)。对于每个 \(k=0,1,\dots,m\),统计满足下面条件的 \(n\) 位 \(10\) 进制数:(允许前导零

  1. 各位数之和不超过 \(k\)。
  2. \(p\) 能整除这个数。

数据范围:\(1\le n\le 10^9,1\le p\le 50,1\le m\le 1000\)。


\(\mathcal{Solution}\)

看到对 \(p\) 的余数相关,就应该想到循环节一类的。以及鸽巢原理。

\(O(npm)\) 的暴力是 navie 的。发现只有 \(n\) 太大不可接受。

注意到,在某些位置上的相同数字可能对 \(w\) 有着这相同的贡献。

具体的,一个数字在第 \(x\) 位上的贡献应该是 \(10^x\bmod p\)。

我们断言,在 \(x\in[1,n]\) 的范围内,这个贡献一定会出现循环节不超过 \(p\) 的混合循环节(若干个循环节和一段长度不超过 \(p\) 的乱序序列组成)。

简单说明一下:首先只要存在两个 \(x,x^\prime\) 使得 \(10^{x}\bmod p=10^{x^\prime}\bmod p\),那么 \(x+1,x^\prime+1\) 也一定满足上面这个等式。由鸽巢原理,在长度不超过 \(p+1\) 的范围内必出现两个\(\bmod p\) 后相等,于是一定存在不超过 \(p\) 的循环节。同理,一开始可能存在一段不属于循环节的部分(比如 \(p=5\)),这部分长度也一定不超过 \(p\)(超过 \(p\) 就一定构成循环节了。

于是,一个想法是,把这些贡献相同的位置合并起来处理,这样就把 \(n\) 降到了 \(p\)。

标签:24,10,le,题解,bmod,循环,NOIP2024
From: https://www.cnblogs.com/CloudWings/p/18536035

相关文章

  • 2024/11/8日 日志 关于Servlet ----(上)
    简介与快速入门点击查看代码--Servlet是Java提供的一门动态web资源开发技术--Servlet是JavaEE规范之一,其实就是一个接口,将来我们需要定义Servlet类实现Servet接口,并由web服务器运行Servlet--publicinterfaceServlet--Definesmethodsthatallservletsmustimpl......
  • 这些实时互动 AI 场景正在涌现生长,也预示着多模态 AI 的未来|RTE2024 声网CEO赵斌演讲
    10月25日,在RTE2024第十届实时互联网大会主论坛上,声网创始人兼CEO赵斌发表了《实时互动十年:从WebRTC到生成式AI时代的RTE》主旨演讲。 赵斌认为,生成式AI正在驱动IT行业发生大变革,这一趋势主要体现在四个层面:终端、软件、云以及人机界面。在这样的时代背景下,生成式......
  • CSP 2024-S 游记 黑暗的枷锁
    09-21今天考完了初赛,明显感觉数学门槛变高了一些,有高中数学知识才能保证看得懂题意,只是苦了小学和初中同学,看数据参加人数还涨了50%,权当拉低分数线了吧。用小图灵估分70。应该是稳过。09-28出分了,刚好70,稳过。竟然和小图灵估的一分不差。10-25复赛前一天晚上,停课的竞赛生们都......
  • [USACO23FEB] Problem Setting P 题解
    [USACO23FEB]ProblemSettingP题目说的很绕,意思就是所有验题人都认为题目难度顺序单增。发现\(m\)很小,很容易想到状压。把H看作\(\tt1\),E看作\(\tt0\),则我们得到\(m\)个长度为\(n\)的\(\tt01\)串,这就是每道题的“状态”。发现状态相同的题没有本质区别,所以我们......
  • 2024网鼎杯-初赛-青龙组
    初赛-青龙组题目附件下载:https://pan.baidu.com/s/1VbieB2XhNYtRqfBeLxguYw?pwd=c03iMiscmisc02​​生蚝:foremost分离,zsteg对最大的png,得到Y3p_Ke9_1s_?????搜7z找到压缩包,然后掩码爆破,得到flag.txt,然后写脚本爆破。得到字符串我们先用foremost分离题目给的flag,因......
  • P11253 [GDKOI2023 普及组] 小学生数学题 题解
    题目传送门前置知识积性函数|乘法逆元解法观察到\(f(i)=\frac{1}{i^{k}}\bmodp\)是完全积性函数,线性筛预处理即可。需要适当的取模优化。代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineullunsignedlonglong#definesortstab......
  • 20241107全国计算机二级Python优秀过级(大头博士计算二级)
    2024年11月7日今天全国计算机二级可以查分了,并下载证书了全国计算机等级考试(NCRE)成绩查询-中国教育考试网查看证书下载证书拿了一张200g的白色卡纸正反打印正反打印,机器有点走墨,晕开了,算了,反正有电子证,打印一张是留着备用的这张证书不能抵扣个人所得税,所以......
  • MLLM_20241101
    Paper1题目:LongVU:SpatiotemporalAdaptiveCompressionforLongVideo-LanguageUnderstanding作者团队:MetaAI,KAUST,KoreaUniversity链接:https://arxiv.org/abs/2410.174341.论文试图解决什么问题?是否是一个新问题?MLLM长视频理解问题。是新问题。2.有哪......
  • 【题解】CF1997
    A首先,插入的字符必须和左右两边的字符都不一样其次,对于插入位置的选择,显然最好插在两个一样的字符中间,如果没有一样的字符,插在最前面即可B观察样例发现题目中要求的位置就在样例中手玩一下,尝试改变样例里那个形状,发现改变任何一个格子都不满足题意,所以得出结论:题目要求的......
  • MLLM_20241025
    Paper1题目:Yo’LLaVA:YourPersonalizedLanguageandVisionAssistant作者:ThaoNguyen,HaotianLiu,YuhengLi,MuCai,UtkarshOjha,YongJaeLee团队:UniversityofWisconsin–Madison(LLaVA原作者团队)链接:https://thaoshibe.github.io/YoLLaVA/1.论文试......