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;
}