首先我们来分析一下

• 按照题意，就是$\frac{w}{2^k}$对mod的取模。
• 分数取模改为逆元取模，逆元可以用费马小定理计算。

最终答案就是(w * fastPower(fastPower(2, k), mod - 2)) % m

所以 $\color{red}Code$:

namespace math{
    typedef long long ll;
    ll fastpow(ll x, ll y, ll mod){
        ll r=1%mod,base=x%mod;
        while(y){
            if(y&1){
                r=r*base%mod;
            }
            base=base*base%mod,y>>=1;
        }
        return r%mod;
    }
    ll gcd(ll x,ll y){
      return y?gcd(y,x%y):x;
    }
    int gcd(int x,int y){
      return y?gcd(y,x%y):x;
    }
}
#include<iostream>
#include<cstdio>
using namespace std;
using namespace math;
ll mod=1e9+7;
int main(){
  ll w,n,k;
  scanf("%lld%lld%lld",&w,&n,&k);
  printf("%lld\n",(w*fastpow(fastpow(2,k,mod),mod-2,mod))%mod);
  return 0;
}

我用 namespace 写的，不必要效仿我。

---

• 分类： 洛谷 题解
• 标签： 洛谷题解
• 浏览： 59