欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

E - Chat Group Gym - 101775A——组合数累加

程序员文章站 2024-03-15 21:21:48
...

It is said that a dormitory with 6 persons has 7 chat groups ^_^. But the number can be even larger: since every 3 or more persons could make a chat group, there can be 42 different chat groups.

Given N persons in a dormitory, and every K or more persons could make a chat group, how many different chat groups could there be?

Input
The input starts with one line containing exactly one integer T which is the number of test cases.

Each test case contains one line with two integers N and K indicating the number of persons in a dormitory and the minimum number of persons that could make a chat group.

1 ≤ T ≤ 100.
1 ≤ N ≤ 109.
3 ≤ K ≤ 105.
Output
For each test case, output one line containing “Case #x: y” where x is the test case number (starting from 1) and y is the number of different chat groups modulo 1000000007.

Example
Input
1
6 3
Output
Case #1: 42

才知道n的所有组合数累加是2n,难怪做不出来,那么只要减去k之前的所有累加就好了。
先预处理阶乘的逆元,否则好像会爆

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
ll ny[100005];
ll n,m;
ll qpow(ll a,ll b)
{
    ll ret=a;
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*ret)%mod;
        ret=(ret*ret)%mod;
        b>>=1;
    }
    return ans;
}
void init()
{
    for(ll i=1;i<=100000;i++)
        ny[i]=qpow(i,mod-2);
}
int main()
{
    int t;
    scanf("%d",&t);
    init();
    int cas=0;
    while(t--)
    {
        scanf("%lld%lld",&n,&m);
        ll ans=qpow(2,n);
        ll cut=1;
        for(int i=0;i<m;i++)
        {
            ans=(ans+mod-cut)%mod;
            cut=(cut*(n-i)%mod*ny[i+1]%mod)%mod;
        }
        printf("Case #%d: %lld\n",++cas,ans);
    }
    return 0;
}
相关标签: 组合