CodeForces Round #191 (327C) - Magic Five 等比数列求和的快速幂取模

很久以前做过此类问题..就因为太久了..这题想了很久想不出..卡在推出等比的求和公式,有除法运算,无法快速幂取模...

看到了

http://blog.csdn.net/yangshuolll/article/details/9247759

才想起等比数列的快速幂取模....

求等比为k的等比数列之和T[n]..当n为偶数..T[n] = T[n/2] + pow(k,n/2) * T[n/2]

n为奇数...T[n] = T[n/2] + pow(k,n/2) * T[n/2] + 等比数列第n个数的值

比如 1+2+4+8 = (1+2) + 4*(1+2)

1+2+4+8+16 = (1+2) + 4*(1+2) + 16

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<set>
#include<algorithm>
#include<cmath>
#define oo 1000000007
#define ll long long
#define pi acos(-1.0)
#define MAXN 505
using namespace std;
char s[100004];
ll m;
ll POW(ll a,ll k)
{
ll x,ans=1;
x=a;
while (k)
{
if (k%2) ans=(ans*x)%oo;
x=(x*x)%oo;
k/=2;
}
return ans;
}
ll T(ll n,ll t)
{
if (n==1) return t;
ll data=T(n/2,t);
data=(data+data*POW(m,n/2))%oo;
if (n%2) data=(data+POW(m,(n-1))*t)%oo;
return data;
}
int main()
{
int k,i;
ll ans,x,len;
while (~scanf("%s",s))
{
scanf("%d",&k);
len=strlen(s);
m=POW(2,len);
ans=0;
x=1;
for (i=0;i<len;i++)
{
if (s[i]=='0' || s[i]=='5')
ans=(ans+x)%oo; // 不要每次都做..加起来
x=(x*2)%oo;
}
ans=T(k,ans); // 只做一次
printf("%I64d\n",ans);
}
return 0;
}
上一篇:VM Depot 镜像新增系列III – 社交媒体,内容管理 与 项目协同系统


下一篇:LODOP选择路径,保存写入word文件