20190820test

Agent

Desciption

IMF(不可能任务小组)有N个Agent，每个Agent的能力值互不相同，现在部长先生想要派出A,B两队Agent去参加特别任务。但是参加大战的两个队伍要满足两个要求：

1. A队中能力最大的Agent的能力值要小于B队能力最弱的Agent的能力值。

2. A,B两队都要有人参加。

并不是所有的Agent都要去参加的，心急的部长先生想知道有多少种安排Agent的方案。由于答案可能很大，所以只需要你求出答案模的值就可以了。

Input

输入仅一行，为一个整数N。

Output

输出答案模的值。

Analysis

这一道题花了一点时间来推，就从$N==6$的情况来讨论一下：

$1.$当$A$组当中只有$1$个的时候一共有: $31+15+7+3+1$种方法，这些都是$2^n-1$,没有什么问题，因为依次取$1,2,3…$你能够选的方案就是这么多，没有什么毛病（就是一个子集的问题，不过排除不选的方案）

$2.$当$A$组当中只有$2$个的时候一共有：$15+7+3+1$种方法吗？不是的，这个时候因为当你选定$A$组最大的那一个的时候，剩余的小的那一个是还有选择的余地的，所以这里并不是这么多，而是要根据排列组合看一看。

$3.$到了这里的时候，差不多就可以看出规律来了，你会发现，这些$2^n-1$的系数，也是$2^x$,没错，这是因为你这样来看的时候，系数都是组合数，加起来就是$2^x$次方了

$4.$化简可以得到式子：
$$
2^0*(2^{n-1}-1)+2^1*(2^{n-2}-1)+……+2^{n-2}(2^1-1)\\
=2^{n-1}(N-1)-2^{n-1}+1
$$
因此代码就呼之欲出了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

//好像找到规律了,但是找到了也一点都不好写 
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll mod=1e9+7;
ll N;

inline ll qkpow(ll b,ll p){
	ll res=1;
	while(p){
		if(p&1)res=res*b%mod;
		b*=b;
		b%=mod;
		p=p/2;
	}
	return res;
}

int main(){
	//freopen("agent.in","r",stdin);
	//freopen("agent.out","w",stdout);
	scanf("%lld",&N);
	ll idx=qkpow(2,N-1);
	ll res=(idx*(N-1))%mod;
	res=res-idx+1;
	printf("%lld",(res+mod)%mod);
	//fclose(stdin);
	//fclose(stdout);
	return 0; 
}