20190820test

Agent

Desciption

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

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

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

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

Input

输入仅一行,为一个整数N

Output

输出答案模img的值。

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
$$
因此代码就呼之欲出了:

//好像找到规律了,但是找到了也一点都不好写 
#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;
}