洛谷P4936 Agent1

题目背景
2018年11月17日，中国香港将会迎来一场XM大战，是世界各地的ENLIGHTENED与RESISTANCE开战的地点，某地 的ENLIGHTENED总部也想派Agent去参加这次的XM大战，与世界其他地方的ENLIGHTENED并肩作战。

题目描述
某地的ENLIGHTENED总部总部有$N$个Agent，每个Agent的能力值互不相同，现在ENLIGHTENED行动指挥想要派出A,B两队Agent去参加XM大战。但是参加大战的两个队伍要满足两个要求：

A队中能力最大的Agent的能力值要小于B队能力最弱的Agent的能力值。
A,B两队都要有人参战。
并不一定所有的Agent都要去参加XM大战的，心急的ENLIGHTENED行动指挥想知道有多少种安排Agent参加大战的方案。由于答案可能很大，所以只需要你求出答案模$(10^9+7)$的值就可以了。

输入输出格式
输入格式：
输入仅一行，为一个整数$N$。

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

输入输出样例
输入样例#1： 
3
输出样例#1： 
5
输入样例#2： 
6
输出样例#2： 
129
说明
对于20%的数据 $N \leq 10$
对于40%的数据 $N \leq 10^3$
 
对于60%的数据 $N \leq 10^5$
 
对于100%的数据 $N \leq 10^9$

唉，不得不感叹自己已经水到写组合数水题的博客了。
不难发现实际上就是求这个
$$\sum^n_{i=2}\binom n i (i-1)$$
然后了解一下乘法分配律和组合数基本化简套路
$$\sum^n_{i=2}\binom n i i - \binom n i \\
=n2^{n-1} + 1 - 2^n$$
做完啦~
~~记事本写题失败~~
```
#include<cstdio>
#define LL long long
using namespace std;
const int mod = 1e9 + 7;

LL fpow(LL a, int b) {
    LL ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return ans;
}

int main() {
    LL n;
    scanf("%lld", &n);
    printf("%lld", (fpow(2, n - 1) * n % mod - fpow(2, n) + 1 + mod) % mod);
    return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链