题目描述
众所周知，一个有着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
此处记住一个定理 组合数 C(n,0)+C(n,1)+……..+C(n,n) =2^n 以此来计算第N个组合数所有可能之和
组合数模板：
C(n,m)= n! / m!*(n-m)!
预处理n(1e5)的阶乘
预处理m(1e5)阶乘的逆元
然后对所有组合数C(n,m) 直接计算分母(n!) × 逆元m！× 逆元(n-m)!
对于此题中，要求从C(n,k)的组合数求和到C(n,n)，直接用组合数模板然后for循环求和会超时，因为会有可能从3遍历到1e9
因为k只到1e5，因此可以利用组合数 总和 2^n 减去前半段0 ~ k-1较短的遍历求出总和，得到ans，后半段的组合数总和
根据组合数n的规律，对于C(n,i) i=0~k-1 可以根据当前值递推出i+1的组合数，将当前值 乘 (n-i+1) 也就是当前分母-1，分子 乘 i 即可得到下一个组合数的值。
这样可以以线性复杂度得到一个组合数N的所有组合值。
#include<stdio.h>
#include<algorithm>
#define LL long long
using namespace std;
const LL MOD=1e9+7;
LL poww(LL x, LL n)///快速幂
{
LL res = 1;
while(n)
{
if(n & 1) res =res*x%MOD;
x = x * x % MOD;
n >>= 1;
}
return res;
}
///组合数模板
LL p[100005],f[100005];///p为阶乘数组，f为阶乘的逆元
void init()///预处理
{
p[0]=1;
for (int i=1;i<=100000;++i)///计算阶乘
p[i]=p[i-1]*i%MOD;
f[0]=1;
for (int i=1;i<=100000;++i)///计算逆元
f[i]=poww(p[i],MOD-2);
return ;
}
LL comb(int n,int m)///计算组合数
{
return (f[m]*f[n-m])%MOD*p[n]%MOD;
}///分子----> n!
///分母----> m!*(n-m)! 计算逆元后相乘得到C(n,m)的组合数
int main()
{
LL k,n;
while(scanf("%lld%lld",&n,&k)!=EOF)
{
LL ans=1;
LL sum=poww(2,n);/// 组合数总和！！！C(n,0)+C(n,1)+......+C(n,n)=2^n
LL tmp=n;
for(int i=2;i<=k;i++)
{
ans=(ans+tmp)%MOD;
// printf("===%lld=====%lld
",tmp,ans);
tmp=((tmp*(n-i+1))%MOD*poww(i,MOD-2))%MOD;///线性计算组合数，分子*n-i+1,分母*i
}
ans=(sum-ans+MOD)%MOD;///减法运算取模，加上MOD再对MOD取模
printf("%lld
",ans);
}///因为题目中计算K到N(1e9) 的组合数计算会超时，因此利用n的组合数总和2^n减去从0到k-1的组合数之和(较短段)，得到后半段k到n组合数之和(较长段)
}
//LL comb(LL n, LL m)///另一种组合数求法，在数塔中斜向求组合数
//{
// if(m > n) return 0;
// LL ret = 1;
// m = min(n - m, m);
// for(int i = 1; i <= m; i ++)
// {
// LL a = (n + i - m) % MOD;
// LL b = i % MOD;
// ret = ret * (a * mod_pow(b, MOD - 2) % MOD) % MOD;
// }
// sum=(sum%MOD+ret%MOD)%MOD;
//}
//
//LL Lucas(LL n, LL m)
//{
// if(m == 0) return 1;
// return comb(n % MOD, m % MOD) * Lucas(n / MOD, m / MOD) % MOD;
//}