codeforces 992 C Nastya and a Wardrobe

codeforces 992 C Nastya and a Wardrobe

​​ Nastya received a gift on New Year — a magic wardrobe. It is magic because in the end of each month the number of dresses in it doubles (i.e. the number of dresses becomes twice as large as it is in the beginning of the month).

Unfortunately, right after the doubling the wardrobe eats one of the dresses (if any) with the 50%50% probability. It happens every month except the last one in the year.

Nastya owns xx dresses now, so she became interested in the expected number of dresses she will have in one year. Nastya lives in Byteland, so the year lasts for k+1k+1 months.

Nastya is really busy, so she wants you to solve this problem. You are the programmer, after all. Also, you should find the answer modulo 109+7109+7, because it is easy to see that it is always integer.

Input The only line contains two integers xx and kk (0≤x,k≤10180≤x,k≤1018), where xx is the initial number of dresses and k+1k+1 is the number of months in a year in Byteland.

Output In the only line print a single integer — the expected number of dresses Nastya will own one year later modulo 109+7109+7.

Examples input Copy 2 0 output Copy 4 input Copy 2 1 output Copy 7 input Copy 3 2 output Copy 21 Note In the first example a year consists on only one month, so the wardrobe does not eat dresses at all.

In the second example after the first month there are 33 dresses with 50%50% probability and 44 dresses with 50%50% probability. Thus, in the end of the year there are 66 dresses with 50%50% probability and 88 dresses with 50%50% probability. This way the answer for this test is (6+8)/2=7(6+8)/2=7.

设初始矩阵为x,1

观察到每次期望会-1/2 所以直接矩阵倍增即可

转移矩阵根据期望计算公式写一下即可

2 0

-1/2 1

#include#define ll long longusing namespace std;const int mod=1e9+7;struct matrix{ int f[3][3];}ans,trans;inline int ksm(ll b,int t){ static ll tmp; for (tmp=1;t;b=b*b%mod,t>>=1) if (t&1) tmp=tmp*b%mod;return tmp;}inline matrix multiply(const matrix &a,const matrix &b){ matrix c;memset(c.f,0,sizeof(c.f)); for (int i=1;i<=2;++i){ for (int j=1;j<=2;++j){ for (int k=1;k<=2;++k){ c.f[i][j]+=(ll)a.f[i][k]*b.f[k][j]%mod; c.f[i][j]%=mod; } } }return c;}ll x,t;int main(){ freopen("c.in","r",stdin); scanf("%lld%lld",&x,&t); if (!x) {puts("0");return 0;} x%=mod;ans.f[1][1]=x;ans.f[1][2]=1; trans.f[1][1]=2;trans.f[2][1]=mod-ksm(2,mod-2); trans.f[2][2]=1; for (;t;trans=multiply(trans,trans),t>>=1) if (t&1) ans=multiply(ans,trans); ans.f[1][1]<<=1;printf("%d\n",ans.f[1][1]%mod); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。