【洛谷 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;
}

后记

这道题其实不算很难吧，主要就是推式子那里麻烦了一点，然后要用到快速幂，其他的也并不是很麻烦，不想用读入优化也是可以的，只是因为比赛的时候想优化一下（其实我还加了八聚氧只不过太长了所以就删掉了）。