微信群(排列组合)
微信群
时间限制: 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;
}
/**/
蓝禾技术公司福利 292人发布
查看21道真题和解析