A - Chat Group Gym-101775A

题目连接:https://codeforces.com/gym/101775/problem/A

题解:就是累加组合数 但是直接由K累加到N肯定会TLE ,所以我们不妨判断不能组成group的情况,即2^n-1(总情况),减去c(n,1)+c(n,2).....c(n,k-1),

这里求组合数的时候要不能直接暴力求解,要用组合数的前后关系 c(n,i)=c(n,i-1)*(n-i+1)/i 这里除以i相当于乘以i的逆元,我们还要对1~1E5的逆元打个表

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1E5+1;
ll ni[N];
ll ksm(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res%mod;
}
int main(){
    int t,k=0;
    cin>>t;
    for(int i=1;i<N;i++)    ni[i]=ksm(i,mod-2);
    while(t--){
        ll n,m;
        k++;
        scanf("%lld%lld",&n,&m);
        ll tmp=1;
        ll ans=0;
        for(int i=1;i<=m-1;i++){
            tmp=(tmp%mod*(n-i+1)%mod)%mod;
            tmp=(tmp%mod*ni[i]%mod)%mod;
            ans=(ans%mod+tmp%mod)%mod;
        }
        printf("Case #%d: %lld\n",k,(ksm(2,n)-1-ans+mod)%mod);
    }
    return 0;
}

 

上一篇:php – 如何知道用户何时关闭浏览器?聊天应用程序


下一篇:php – 聊天应用程序AJAX轮询