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

很久以前做過此類問題..就因為太久了..這題想了很久想不出..卡在推出等比的求和公式，有除法運算，無法快速冪取模...

才想起等比數列的快速冪取模....

求等比為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;
}