【洛谷 P6195】 迫害

题目传送门

这道题，乍一看很难，但其实就是一道推结论的数学题。

相信大家在小学的时候都做过这样一道数学题吧：大意就是如何用最少的正整数凑出最多的连续的正整数（随便口胡了一下，差不多就行了），其思路大致如下：

先取 $1$ ，因为这是最小的正整数。
再取 $2$ ，因为一个 $1$ 凑不出 $2$ 。
再取 $4$ ，因为 $1+2=3$ ，无法凑出 $4$ 。
再取 $8$ ，因为 $1+4=5,2+4=6,1+2+4=7$ ，凑不出 $8$ 。
$\cdots$

由此，我们可以看出一个规律，当每次取前面取过的所有数的和再加一时，可以凑出最多的正整数，即：

$m_i=\sum\limits_{j=1}^{i-1}m_j+1$

铺垫完毕。

过程

接下来我们进入这道题的分析。

根据上述规律，我们可以看出，这道题其实也有着异曲同工之妙，由于有 $m$ 个数可以取任意值，我们就按照以上策略来取（由于 $n$ 代表的是有 $n$ 个 $1$ ，所以可以当成是补漏的），设 $x_i$ 表示第 $i$ 次取的值，则有：

$x_1=n+1$

$x_2=x_1+n+1=2\cdot n+2=2\cdot(n+1)$

$x_3=x_1+x_2+n+1=4\cdot n+4=4\cdot(n+1)$

$x_4=x_1+x_2+x_3+n+1=8\cdot n+8=8\cdot(n+1)$

$\cdots$

$x_m=2^{m-1}\cdot(n+1)$

此时，我们能表示出来的从 $1$ 开始的连续的正整数就有这么多：

$\sum\limits_{i=1}^m x_i+n$

即：

$(1+2+4+8+\cdots+2^{m-1})\cdot(n+1)+n$

怎么样，前面那个式子是不是似曾相识？没错，这是我们小学所学的等比数列！只要把最后的 $n$ 变成 $n+1-1$ ，并把 $n+1$ 合并到前面的那一坨东西里面，就可以弄出这个式子：

$2^m\cdot(n+1)-1$

具体过程我不详细解释了，比较简单，手推一下就行了。既然都弄出了这个式子，那我们就可以偷税地去算了。

对了，由于 $m\le 10^9$ ，直接暴力算乘方明显会超时，所以我们需要用快速幂（不会的同学建议去做一下这道题）。

参考代码

#include<bits/stdc++.h>
#define ll long long
#define p 1000000007
using namespace std;
ll n,m,t;
inline ll input()//读入优化
{
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
	{
        if(c=='-')
			f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
	{
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
inline ll ksm(ll b,ll k)//快速幂
{
	ll ans=1;
	while(k)
	{
		if(k&1)//快速幂里面的位运算，相当于 k%2==1
			ans=ans*b%p;
		b=b*b%p;
		k>>=1;//同上，相当于 k/=2
	}
	return ans%p;
}
int main()
{
 	n=input();//读入优化不解释
 	m=input();
 	printf("%lld",ksm(2,m)*(n+1)%p-1);//记得取模啊！！！
	return 0;
}