cf 327c magic five 等比数列求和+求逆元 + 快速指数幂 使用 费马小定理求逆元

题意

        给你个板子板子上有一串数（一个字符串str+字符串重复的次数）让你去掉任意的数（不能全删）使之成为能够被5整除的数，问共有多少种方

        法（%1000000007）m= 1000000007

        PS   1） 允许有前导0

                2） 板子上不同位置的数去掉是不同的答案  比如 115 去掉第一个1和去掉第二个1是两种方法

分析

    1）可以被5整除的数：结尾为0或者5的数即可被5整除

    2）删除的方法：当第I位数为5或者0时  那么一共有2^i种方法(i起始于0)

                               一个str（不算重复的）中共有    a{1} = 2^0*(str[0]==5||str[0]==0)+……+2^i*(str[i]==5||str[i]==0).......

                               所有str（算上重复的）构成等比数列 

                                a{n}=a{1}*q^(n-1)

                                其中 q= 2^strlen(str).

                                和值:  sum = (a{1} *(q^n-1  )/(q-1) )%m

分析结果

        我们需要求的就是    sum = a{1} *(q^n-1  )/(q-1) %m 但是有两个重点问题需要解决

        1）求指数运算比较大直接算会超时： 可以使用快速指数幂来进行求快速的求解

        2）对于sum的球模 中间会有除法： 让我们想到求逆元使之变成乘法运算 

        3）转换为乘法：见下文中的费马定理求逆元之后

 

 

快速指数幂

       网上有很多 讲的很好 直接百度过来

      

        1）定义

快速幂顾名思义，就是快速算某个数的多少次幂。

其时间复杂度为 O(log2N)， 与朴素的O(N)相比效率有了极大的提高。

以下以求a的b次方来介绍

2）原理

把b转换成2进制数

该2进制数第i位的权为（2^(i-1)）

例如

a^11=a^(2^0+2^1+2^3)

11的二进制是1 0 1 1

11 = 2^3*1 + 2^2*0 + 2^1*1 + 2^0*1

因此，我们将a^11转化为算a^(2^0)*a^(2^1)*a^(2^3)

3）代码比较

常规求幂

int pow1( int a, int b ) {

int r = 1;

while( b-- )

r *= a;

return r;

}

二分求幂（一般）

int pow2( int a, int b ) {

int r = 1, base = a;

while( b != 0 ) {

if( b % 2 )

r *= base;

base *= base;

b /= 2;

}

return r;

}

快速求幂（位操作）

int pow3( int a, int b ) {

int r = 1, base = a;

while( b != 0 ) {

if( b & 1 )

r *= base;

base *= base;

b >>= 1;

}

return r;

}

费马定理求逆元

       费马小定理是数论中的一个重要定理，其内容为： 假如p是质数，且gcd(a,p)=1，那么 a^(p-1) ≡1（mod p） 假如p是质数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1

 

上面的分析结果

转换为乘法      

            我们要求

                         sum = a{1} *(q^n-1  )/(q-1) %m

                         sum = a{1}%m*( (q^n-1)/(q-1))%m

                         其中a{1}%m很好算

                         剩下的问题只是temp= ( (q^n-1)/(q-1))%m

                         为了方便起见 设 x=(q^n-1)       y=(q-1)   y的逆元为yy(别急一会儿求)

                         剩下的问题就变成了求     temp=(x/y)%m  

                         已知逆元 y*yy%m==1(逆元的知识自己百度吧)

                          temp= (x/y)%m  = (x/y)%m *(y*yy)%m = （（x/y）*(y*yy)）%m = (x*yy)%m

                          已知 gcd(y,m)=1 且 m是质数

                          由小费马定理可以知道

                          y^(m-1)%m=(  y*y^(m-2)   )%m=1

                          因此 y的逆元 即yy =y^(m-2)

                          又因为 temp = (x*yy)%m 

                           所以  temp =   (x*y^(m-2))%m

                          所以SUM = (a{1}*(x*y^(m-2)))%m

                               = (a{1}*( (q^n-1)* (q-1) ^(m-2)))%m

   所以：：：：把sum用快速指数幂算一遍就行了··············

                           

      AC代码：                   

 

#include<iostream>
#include<cstdio>
#include<stdlib.h>
#include<cstring>
using namespace std;
const long long M = 1000000007; 
long long pow3( long long a, long long b ) {
	long long r = 1, base = a;
	while( b != 0 ) {
		if( b & 1 )
			r = (r*base)%M;
		base = ( base * base ) % M;
		b >>= 1;
	}
	return r;
}
int main()
{
	char s[300000];
	long long n;
	while(gets(s))
	{
		cin>>n;
		getchar();
		long long sLen = strlen(s);
		long long sum = 0;
		long long base = 1;
		for(int i=0;i<sLen;i++)
		{
			if( s[i]=='0' || s[i] == '5' )
			{
				sum = ( sum + base )%M;
			}
			base = (base * 2)%M;
		}
		long long q = pow3(2,sLen);
		long long a1 = sum;
		int top = (pow3(q,n)+M-1)%M;
		int buttom = pow3((q+M-1)%M,M-2)%M;
		sum = (a1*top)%M;
		sum = (sum*buttom)%M;
		cout<<sum<<endl;
		
	}
}