CodeForces 992C Nastya and a Wardrobe（规律、快速幂）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

http://codeforces.com/problemset/problem/992/C

题意：

给你两个数x，k，k代表有k+1个月，x每个月可以增长一倍，增长后的下一个月开始时x有50%几率减1，增长k+1个月后结果是每种情况的总和除以种数。

题目要求的是增长k+1个月后的结果。

我们根据第三个样例可以推出他的增长过程

1211109

| | ||

24 22 2018

从这个推导我们容易得出最后得到的每种情况构成一个等差数列，公差为2

结果是：（2*n-1）*2^k+1

注意特判0的情况，0的时候答案是0，直接输出

另外求2的次方的时候用快速幂，注意取余

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>
const int INF=0x3f3f3f3f;
typedef long long LL;
const int mod=1e9+;
//const double PI=acos(-1);
#define Bug cout<<"---------------------"<<endl
const int maxm=1e6+;
const int maxn=1e5+;
using namespace std; LL POW(LL a,LL b )
{
LL ans = ;
a = a % mod;
while(b)
{
if( b % == )
ans = ( ans * a ) % mod;
a = ( a * a ) % mod;
b /= ;
}
return ans;
} int main()
{
LL n,k;
scanf("%lld %lld",&n,&k);
LL ans=;
if(n!=)
{
n=n%mod;
ans=(((*n-)*POW(,k)+mod)%mod++mod)%mod;
}
printf("%d\n",ans);
return ;
}