P4936 Agent1 题解

题意

给定一个整数 $n$，代表有 $n$ 个数（不妨设为 $1,2,\dots ,n$）。

让你把这些数分为两组（考虑直接左右切成两半），其中每一组要保证有数，每一个数不一定要用。

求有多少种分组方式。

答案对 $1000000007$ 取模。

推导

对于 $n$ 个数，我们有 $n$ 种切割方法。考虑对于第 $i$ 种切割（切割的临界值要选，归为），每一个数可选可不选，所以左边一组共有 $2^{i-1}$ 种选法，右边有 $2^{n-i}-1$ 种选法。

$\begin{array}{rl}ans& =\sum _{i=1}^n{2}^{i-1}\times (2^{n-i}-1)\\ & =\sum _{i=1}^n{2}^{n-1}-2^{i-1}\\ & =(n-2)\times 2^{n-1}+1\end{array}$

代码

$16$ 行代码，如果需要可以压到 $14$ 行。

#include<bits/stdc++.h>
long long m,mod=1000000007,ans=1;
void fastpow(long long a,long long b)
{
	while(b)
	{
		if(b&1) ans=(ans*a)%mod,b--;
		b/=2,a=a*a%mod;
	}
}
int main()
{
	scanf("%lld",&m),fastpow(2,m-1);
	printf("%lld",(m-2)*ans%mod+1);
	return 0;
}