codeforces magic five －－快速幂模

时间：2023-03-08 17:35:18

题目链接：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-;

 char a[];

 const int MOD=;

 #define LL long long

 int k;

 LL quick(LL a, LL b) {

     LL ans=;

     while (b) {

         if(b&) ans=(ans*a)%MOD; b/=; 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(,n*k)-+MOD; a=(a+MOD)%MOD;

     LL b=quick((quick(,n)-+MOD)%MOD,MOD-); b=(b+MOD)%MOD;

     LL ans=;

     for(size_t i = ; i < n; ++i) if (s[i]==''||s[i]=='') ans=(ans+quick(,i))%MOD;

     cout<<a*b%MOD*ans%MOD<<endl;

     return EXIT_SUCCESS;

 }                /* ----------  end of function main  ---------- */

搞定，收工

相关文章