题解 P6195 【迫害】

形象的描述:

题解 P6195  【迫害】

比赛的时候我这题就乱搞一通,但是过了。

接下来是正题:

分析:

一开始我想到的是类似于P1021 邮票面值设计的做法,但后来看看数据太大,就感觉应该有规律,就开始尝试推式子。

分析题目,我们发现,假如前 \(s\) 个人都能被连续迫害,要想让迫害的人更多,那么下一个让 xht37 X 选择的数字就是 \(s+1\)。

为什么?因为如果 \(1,2,3\ldots\ldots s-1,s\) 能*害,再加一个数字 \(a\) 之后,\(1+a,2+a,3+a\ldots\ldots s-1+a,s+a\) 同样也能*害。当 \(a\) 为 \(s+1\) 时,就能保证从 \(1\) 到 \(2\times s+1\) 的人都能*害。这样一来,取 \(s+1\) 就能保证迫害的人最多。

STEP1:

那么就可以用递推来解决了:\(f_i\) 表示选择第 \(i\) 个自定义数字时,连续迫害的人数。初始条件为 \(f_0=n\),公式为 \(f_i=2\times f_{i-1}+1\)。\(f_m\) 就是最终结果。

因为 \(m\) 太大,我们就用两个变量迭代来代替数组。

递推的代码如下:

#include<bits/stdc++.h>
using namespace std;
#define rg register
int n,m;
long long a,b;
int main()
{
	cin>>n>>m;
	a=n;  //初始化。
	for(rg int i=1;i<=m;++i)  //迭代版的递推。
	{
		b=(2*a+1)%1000000007;
		a=b;
	}
	cout<<b;
   return 0;
} 

那么满怀信心交上去:

题解 P6195  【迫害】

嗯,超时呢 \(\ldots\ldots\)

STEP2:

那我就想能否求出通项公式。

\[f_i=2\times f_{i-1}+1 \]

两边同时加 \(1\),得:

\[f_i+1=2\times f_{i-1}+1+1 \]

即:

\[f_i+1=2\times (f_{i-1}+1) \]

欸,这不就是等比数列吗!

那么等比数列的通项公式是什么?

\[f_i=f_1\times q^{n-1} \]

这里的 \(q\) 是什么? \(2\) !

这里的 \(f_1\) 是什么? \(2\times n+1\) !

那么通项公式就出来了:

\[f_m=(2\times n+1)\times 2^{m-1}-1 \]

即:

\[f_m=(n+1)\times 2^m-1 \]

PS:因为 \(m\) 太大,注意一下求幂的时候用快速幂。

敲可爱的完整 AC 代码:

#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long quick_power(long long base,long long n)  //快速幂。 
{
	long long res=1;
	while(n>0)
	{
		if(n&1)
			res=res*base%1000000007;
		base=base*base%1000000007;
		n>>=1;
	}
	return res;
}
int main()
{
	cin>>n>>m;
	cout<<((n+1)*quick_power(2,m)-1)%1000000007;  //真正的代码只有 3 行。 
	return 0;
} 

一个初一小蒟蒻写题解也不容易,点个赞吧。

上一篇:Linux系统安全及应用


下一篇:Entropy, relative entropy and mutual information