BZOJ2839集合计数

#include<iostream>
#include<cstdio>
#define N 1000009
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll inv[N],jie[N],ni[N],n,k,ans;
inline ll power(ll x,ll y){
    ll ans=1;
    while(y){
        if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1;
    }
    return ans;
}
inline ll C(int n,int m){
    return jie[n]*ni[m]%mod*ni[n-m]%mod;
}
int main(){
    cin>>n>>k;
    inv[0]=1;
    for(int i=1;i<=n;++i)inv[i]=inv[i-1]*2%(mod-1);
    jie[0]=1;
    for(int i=1;i<=n;++i)jie[i]=jie[i-1]*i%mod;ni[n]=power(jie[n],mod-2);
    for(int i=n-1;i>=0;--i)ni[i]=ni[i+1]*(i+1)%mod;
    for(int i=k;i<=n;++i){
         if((i-k)&1)ans-=C(n-k,i-k)*(power(2,inv[n-i])-1)%mod;
         else ans+=C(n-k,i-k)*(power(2,inv[n-i])-1)%mod;
         ans=(ans%mod+mod)%mod;
    }
    ans=ans*C(n,k)%mod;
    cout<<ans;
    return 0;
}