codeforces Magic Five

本文从WordPress迁移而来, 查看全部WordPress迁移文章

http://codeforces.com/contest/327/problem/C

数论
题意:给出一串数字,下面是它的重复次数,从而组成一个大数。在这个大数里删除一些数字,使剩下的数字能被5整除。问有多少种方案,结果模10^9+7

思考:

  1. 先来考虑一个数字,能被5整除,则尾数为0或5,因为不是0或5的数字肯定不能作为尾数
  2. 确定删除后的尾数的方法来计算。原数字的第x位是0或5,如果以这一位作为删除后的数字的最后一位,那么原数字的x位后面 的数字要全部删除。那么1到x-1位的数字有多少删除方法呢?就是求一下子集个数————把1到x-1这些数字看成一个集合,在这个集合中无论选出什么数字,再在最后加上第x个数字,一定能被5整除,所以子集个数为2^(x-1)
  3. 所有扫描一次整个串,把所有为0,5的数字所处点的位置找出来,计算子集个数后全部累加起来即可
  4. 但是串的长度太大(重复的原因),不能一个一个扫描下去
  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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
#define mod 1000000007
#define ll long long

ll rep,ans,S;
string str;

ll pow_mod(ll a ,ll n){
if(n == 0LL) return 1LL;
if(n == 1LL) return a;
ll temp = pow_mod(a,n >> 1);
temp = ( temp * temp) % mod;
if(n & 1LL) temp = (temp * a) % mod;
return temp;
}

ll cal_S(ll m , ll n){
// S = ( 2^0 + 2^(n) + 2^(2n) + 2^(3n) + 2^(4n) ....... + 2^(mn) ) % mod;
// S = ( ( 2^[(m+1)n] - 1 ) / (2^n - 1) ) % mod;
// S = ( ( 2^[(m+1)n] - 1 ) * (2^n - 1)^(mod - 2) ) % mod; //消掉除法
ll t1 = pow_mod(2 , (m + 1LL)*n) % mod - 1;
ll t2 = pow_mod(pow_mod(2 , n)-1 , mod - 2) % mod;
ll t3 = (t1 * t2) % mod;
return t3;
}

int main(){
ans = 0;
cin >> str >> rep;
S = cal_S(rep - 1LL , (ll)str.length());
//cout << "S = " << S << endl;
for(int i = 0; i < str.length(); i++)
if(str[i] == '0' || str[i] == '5'){
ll p1 = pow_mod(2 , (ll)i);
ans = (ans + p1) % mod;
}
ans = (ans * S) % mod;
cout << ans << endl;
return 0;
}