codeforces-922C-Nastya and a Wardrobe

传送门：https://codeforces.com/contest/992/problem/D

题意：一个人的衣橱里有n件衣服,一年有k+1个月，每个月衣橱里的衣服都会翻番，前k个月每个月衣服都有一半几率会-1，问最后还剩多少件衣服

建议手动模拟找规律

举个栗子 n=3,k=3,(每个月都翻番或翻番再减一）

第一个月：5 6

第二个月：9 10 11 12

第三个月：17 18 19 20 21 22 23 24

第四个月：34 36 38 40 42 44 46 48

因为每分一次几率都是对半劈的，所以等于每个数的几率都相等，取平均值就可以

然后我们可以发现平均值就是这组数的最中间的那个数（40+42）/2，就等于边界两个数相加除以2

最右面的数是没有减过一的，b=n*(2^(k+1))

最左面的数是a=b-(2^(k+1)-2)

相加除以2，约吧约吧就出答案了，一个快速幂就可以解决

再就是n和k都有可能等于0，特判一下

乌拉~

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const ll mod=1e9+7;
 5 ll fpow(ll a,ll b,ll c)
 6 {
 7     ll ans=a;
 8     for(b--;b>0;b>>=1,a*=a%c,a%=c)
 9     if(b&1) ans*=a%c,ans%=c;
10     return ans%c;
11 }
12 int main()
13 {
14     ll x,k;
15     scanf("%lld%lld",&x,&k);
16     if(x==0) printf("0
");
17     else if(k==0) printf("%lld
",x*2%mod);
18     else printf("%lld
",((x%mod)*fpow(2,k+1,mod)%mod-fpow(2,k,mod)+1+mod)%mod);
19     return 0;
20 }