本文从WordPress迁移而来, 查看全部WordPress迁移文章
http://codeforces.com/contest/327/problem/C
数论
题意:给出一串数字,下面是它的重复次数,从而组成一个大数。在这个大数里删除一些数字,使剩下的数字能被5整除。问有多少种方案,结果模10^9+7
思考:
- 先来考虑一个数字,能被5整除,则尾数为0或5,因为不是0或5的数字肯定不能作为尾数
- 确定删除后的尾数的方法来计算。原数字的第x位是0或5,如果以这一位作为删除后的数字的最后一位,那么原数字的x位后面 的数字要全部删除。那么1到x-1位的数字有多少删除方法呢?就是求一下子集个数————把1到x-1这些数字看成一个集合,在这个集合中无论选出什么数字,再在最后加上第x个数字,一定能被5整除,所以子集个数为2^(x-1)
- 所有扫描一次整个串,把所有为0,5的数字所处点的位置找出来,计算子集个数后全部累加起来即可
- 但是串的长度太大(重复的原因),不能一个一个扫描下去
- 一块串的长度为n,一块串的第x位是0或5,那么可知重复后,第x+n位,第x+2n位,第x+3n,第x+4n位都是这个数字
第x位前面的数字个数为x-1,能产生的子集个数是2^(x-1)
第x+n位前面的数字个数为x-1+n,能 产生的子集个数为2^(x-1+n)
………………………………………………
第x+mn位前面的数字个数为x-1+mn,能产生的子集个数为2^(x-1+mn)
那么先来计算这个数字,以及它的重复的情况能产生多少种方案
2^(x-1) + 2^(x-1+n) + 2^(x-1+2n) + 2^(x-1+3n) + 2^(x-1+4n) ………….. + 2^(x-1+mn)
= 2^(x-1) * [ 2^0 + 2^n + 2^(2n) + 2^(3n) + 2^(4n) ………… + 2^(mn) ]
= 2^(x-1) * S
看看怎么计算S
S = 2^0 + 2^n + 2^(2n) + 2^(3n) + 2^(4n) ………… + 2^(mn)
2^n*S = 2^n + 2^(2n) + 2^(3n) + 2^(4n) ………… + 2^(mn) + 2^[(m+1)n]
下式 - 上式,就能把中间的部分消掉
(2^n - 1) * S = 2^[(m+1)n] - 2^0 = 2^[(m+1)n] - 1
S = (2^[(m+1)n] - 1) / (2^n - 1)
(计算S的方法就是高中数学的常用方法嘛,叫什么名字忘记了…….错位相减?)
回到原式 = 2^(x-1) * S ; S已经计算出来了
注意我们的原式最后是要模10^9+7,即
原式 = (2^(x-1) S) % m = ( 2^(x-1) % m S % m ) % m
这里 有一个关键的转化 S % m
注意到S的计算公式中用了除法,这是危险的;另外m是10^9 + 7,是一个素数,可以用费马小定理,将除法转化为乘法
S % m = [ (2^[(m+1)n] - 1) / (2^n - 1) ] % m = [ (2^[(m+1)n] - 1) (2^n - 1)^(m-2) ] m
至此,全部问题都解开了
1 |
|