codeforces magic five －－快速幂模

July 19, 2013
CodeForces Math

题目链接：http://codeforces.com/contest/327/problem/C 首先先算出一个周期里面的值，保存在ans里面，就是平常的快速幂模m做法．然后要计算一个公式，比如有k个部分，那么对于没一个位置i, 都有2^i + 2^(i+n) + … + 2^(i+(k-1)*n) = 2^i(1 + 2^n + … + 2^((k-1)*n)) = 2^i * (1-2^(n*k))/(1-2^n) 所以结果就是ans * (1-2^(n*k))/(1-2^n) % MOD; 然后就是关键计算(1-2^(n*k))/(1-2^n) % MOD；用到费马小定理a^(p-1)同余于1(mod 1)．p是一个质数，那么a^(p-2) * a 同余于１(mod 1) ，所以a 的逆元就是 a^(p-2) MOD是一个质数,所以(1-2^(n*k))/(1-2^n) % MOD = (2^(n*k)-1)/(2^n-1) % MOD = (2^(n*k)-1)%MOD * ((2^n-1)^(MOD-2))%MOD


/*
 * =====================================================================================
 *       Filename:  magic.cpp
 *        Created:  19/07/2013 12:27:18
 *         Author:  liuxueyang (lxy), 1459917536@qq.com
 *   Organization:  Hunan University
 *
 * =====================================================================================
 */

/*
ID: zypz4571
LANG: C++
TASK: magic
*/
#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <list>
using namespace std;
#define INF 0x3f3f3f3f
const double eps=1e-9;
char a[100010];
const int MOD=1000000007;
#define LL long long
int k;
LL quick(LL a, LL b) {
    LL ans=1;
    while (b) {
        if(b&1) ans=(ans*a)%MOD; b/=2; a*=a; a%=MOD;
    }
    return ans;
}
int main ( int argc, char *argv[] )
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int k; string s; cin>>s>>k; LL n=s.size();
    LL a=quick(2,n*k)-1+MOD; a=(a+MOD)%MOD;
    LL b=quick((quick(2,n)-1+MOD)%MOD,MOD-2); b=(b+MOD)%MOD;
    LL ans=0;
    for(size_t i = 0; i < n; ++i) if (s[i]=='0'||s[i]=='5') ans=(ans+quick(2,i))%MOD;
    cout<<a*b%MOD*ans%MOD<<endl;
    return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */

搞定，收工

Read more