题目描述

某地的总部有$N$个$Agent$,每个$Agent$的能力值互不相同。

现在行动指挥想要派出$A,B$两队$Agent$去参加$XM$大战。

但是参加大战的两个队伍要满足两个要求:

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

②$A,B$两队都要有人参战。

并不一定所有的$Agent$都要去参加$XM$大战的,心急的行动指挥想知道有多少种安排$Agent$参加大战的方案。

由于答案可能很大,所以只需要你求出答案模$(10^9+7)$的值就可以了。

输入格式

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

输出格式

输出答案模$(10^9+7)$的值。

样例输入

6

样例输出

129

数据范围

对于$100\%$的数据$N \leq 10^9$

菜鸡的咆哮

这是一道数列大题$QwQ$

我们令$a_n$表示有$n$个$Agent$时的作战方案数。

显然$a_1=0$($A,B$两队都要有人参战)。

考虑加入一个新的$Agent$后增加的方案:

①在$n-1$的情况下将其放在每种情况的$B$组中:$a_{n-1}$种方案。

②单独放在$B$组,$A$组在剩下的$n-1$个中任意选择:

排除$A$组为空的情况后共有$2^{n-1}-1$种方案。

于是我们可以写出递推式:

$$ a_n=2\times a_{n-1}+2^{n-1}-1\ \ \ \ \ (a_1=0) $$

因为$N \leq 10^9$,$O(n)$肯定要超时。

所考虑写出它的通项:

两边同除$2^n$得

$$ \frac{a_n}{2^n}=\frac{a_{n-1}}{2^{n-1}}+\frac{1}{2}-\frac{1}{2^n} $$

令$b_n=\frac{a_n}{2^n}$移项得

$$ b_n-b_{n-1}=\frac{1}{2}-\frac{1}{2^n} $$

列项相加得

$$ b_n-b_{1}=\frac{n-1}{2}-(\frac{1}{2^2}+\frac{1}{2^3}+...\frac{1}{2^n}) $$

进一步转化得

$$ b_n-b_{1}=\frac{n}{2}+\frac{1}{2^n}-1 $$

将$\frac{a_n}{2^n}=b_n$代入变形得

$$ a_n=(n-2)\times2^{n-1}+1\ \ \ \ \ (n\ge 1) $$

快速幂解决。

就当复习数列通项了$QwQ$

代码

#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
using namespace std;
int n;
ll qkpow(int n,int m){
    ll ans=1,base=n;
    while(m){
        if(m&1) ans*=base,ans%=mod;
        base*=base;base%=mod;
        m>>=1;
    }
    return ans;
}
int main(){
    //freopen("agent.in","r",stdin);
    //freopen("agent.out","w",stdout);
    scanf("%d",&n);
    printf("%d\n",((n-2)*qkpow(2,n-1)+1)%mod);
    return 0;
}