Codeforces 327C 快速幂+等比数列求和+乘法逆元

本文主要是介绍Codeforces 327C 快速幂+等比数列求和+乘法逆元，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://codeforces.com/problemset/problem/327/C
There is a long plate s containing n digits. Iahub wants to delete some digits (possibly none, but he is not allowed to delete all the digits) to form his “magic number” on the plate, a number that is divisible by 5. Note that, the resulting number may contain leading zeros.

Now Iahub wants to count the number of ways he can obtain magic number, modulo 1000000007 (109 + 7). Two ways are different, if the set of deleted positions in s differs.

Look at the input part of the statement, s is given in a special form.

Input
In the first line you’re given a string a (1 ≤ |a| ≤ 105), containing digits only. In the second line you’re given an integer k (1 ≤ k ≤ 109). The plate s is formed by concatenating k copies of a together. That is n = |a|·k.

Output
Print a single integer — the required number of ways modulo 1000000007 (109 + 7).

题意

有一个循环了n次字符串a，a中的字符均为数字。
现在要删去其中的若干字符（不能全删），使得最后剩下的数字是5的倍数。

思路

先说一个基本但必须用到的结论：若一个数是5的倍数，则它末位是5的倍数（即为5或0）。
设这个字符串为a[1]a[2]a[3]...a[p]...a[n]。
首先需要思考一个问题：以a[p]结尾的数有多少个。
答案是：2^(p-1)。
这个的推导过程很简单，这里就不赘述了。
并注意：数据过大，需要快速幂。然后要想一个问题：由于循环次数n过大，从前到后枚举一次不现实，需要用数学方法简化。
由于它循环n次每次都是相同的字符串，所以易得
以a[p]结尾的数个数+以a[p+len]结尾的数个数+...+a[p+len*(n-1)]
=2^(p-1)+2^(p+len-1)+...+2^(p+len*(n-1)-1)
=2^(p-1)*[2^0+2^len+...+2^(len*(n-1))]
然后用等比数列求和公式化简，得
原式=2^(p-1)*(2^(len*n)-1/2^len-1)。现在又面临一个更大的问题：
结果需要对10^9+7取模，但是在上式分母上下都是快速幂，取模后会有精度丢失的问题。
所以需要引进乘法逆元来完成。乘法逆元的定义是：如果ab≡1 (modp)，则说b是mod p意义下的乘法逆元。
在此题中，需要求(a/b)%p的值，则设k是b的乘法逆元，则(a/b)%p=(a*k)%p。
这个等式的证明可以看这篇题解：
http://www.cnblogs.com/tiankonguse/archive/2012/08/14/2638949.html
而求b的乘法逆元可以运用费马小定理：
由b^(p-1)≡1 (modp)，得b的乘法逆元是b^(p-2)。
所以问题就解决了。PS.变量最好用long long，如果一个int和一个long long相乘可能会出错。

代码

#include<stdio.h>
#include<cstring>
using namespace std;
const long long mod=1000000007;
long long fastpow(long long b,long long p,long long k) {b%=k;long long ret=1;while(p) {if(p&1) ret=(ret%k)*(b%k)%k;p>>=1;b=(b%k)*(b%k)%k;}return ret%mod;
}
char a[1000001];
int main() {
//  freopen("data.txt","r",stdin);long long k,len;gets(a);scanf("%I64d",&k);len=strlen(a);long long ans=0;for(int i=0; i<len; i++) {if(a[i]=='5' || a[i]=='0') {ans=(ans+fastpow(2,i,mod))%mod;}}long long tmp=fastpow(2,len,mod)%mod;long long p=fastpow(2,len*k,mod)%mod;tmp=((1-tmp)%mod+mod)%mod;tmp=fastpow(tmp,mod-2,mod);p=((1-p)%mod+mod)%mod;ans=(ans*p)%mod*tmp%mod;
//  if(a[0]=='8' && a[1]=='4')  printf("%I64d %I64d ",tmp,p);printf("%I64d",ans);return 0;
}
/*
27755776656210607832788619414635535178188775623838313967013958143619017005079991285469853503718562504927535176713879737569375166451462839457844835806559098448980069427607
151
*/