【题解】「NOIP2024模拟赛24 T3」钙绿
https://www.becoder.com.cn/contest/5715/problem/3
\(\mathcal{Description}\)
给定 \(n,p,m\)。对于每个 \(k=0,1,\dots,m\),统计满足下面条件的 \(n\) 位 \(10\) 进制数:(允许前导零
- 各位数之和不超过 \(k\)。
- \(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