微信群(排列组合)

微信群

时间限制: 1 Sec  内存限制: 128 MB

题目描述

众所周知，一个有着6个人的宿舍可以有7个微信群（^_^，别问我我也不知道为什么），然而事实上这个数字可以更大，因为每3个或者是更多的人都可以组建一个群，所以6个人最多可以组建42个不同的群。
现在，已知一间宿舍有N个人，并且每至少K个人都可以组建一个微信群，那么他们最多可以组建多少个不同的微信群？

输入

一行两个整数N和K，表示宿舍中的人数和最少能够组建微信群的人数

输出

一行一个整数，即最多能组建多少个不同的微信群，由于这个数字很大，请输出对10^9+7求余后的结果

样例输入

复制样例数据

6 3

样例输出

42

提示

对于30%的数据，3<=N<=10^3
对于60%的数据，3<=N<=10^6
对于100%的数据，3<=N<=10^9，3<=K<=10^5

有一个排列组合的公式。

这道题目求

注意最后可能为负。。。

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

LL n;
int k;
const long long mod = 1e9 + 7;

LL pow_c(LL x, int num){
	LL res = 1 % mod;
	x %= mod;
	while(num){
		if(num & 1) res = (res * x) % mod;
		x = (x * x) % mod;
		num >>= 1;
	}
	return res;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%lld %d", &n, &k);
	LL ans = pow_c((LL)2, n), sum = 1, t = 1;
	for (int i = 1; i < k; i++){
		t = t * (n - i + 1) % mod * pow_c((LL)i, mod - 2) % mod;
		sum = (sum + t) % mod;
	}
	
	ans = ((ans - sum) % mod + mod) % mod;
	printf("%lld\n", ans);

	return 0;
}
/**/