A
I'am crazy now.
I was wa for many times for a little problem
ans will be litter than sum sometime and I forget make it a positive integer
ans = (ans - sum + mod) % mod;
This is a easy problem that we should get the answer
\(\sum_{i=k}^{n}C(i,n)\)
\(=C_{n}^{k}+ \cdots + C_{n}^{n} \\= (C_{n}^{0}+ C_{n}^{1} + \cdots + C_{n}^{n}) - (C_{n}^{0}+ C_{n}^{1} + \cdots + C_{n}^{k-1})\)
as we know that
\[2^n = (1+1)^{n} = C_{n}^{0} \times 1^{0} \times 1^{n} + C_{n}^{1} \times 1^{1} \times 1^{n-1} + \cdots + C_{n}^{n} \times 1^{n} \times 1^{0} = C_{n}^{0} + C_{n}^{1} + \cdots + C_{n}^{n}\]
so the answer is
\(2^{n} - (C_{n}^{0}+ C_{n}^{1} + \cdots + C_{n}^{k-1})\)
\(C_{n}^{k}÷ C_{n}^{k-1}= \frac{n-k+1}{k}\)
Do't forget the inv() in fraction
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const int mod = 1000000007;
ll pow(ll a,ll b,ll p){
ll ans = 1;
a = a % mod;
while(b){
if(b&1)ans = ans * a % p;
b >>= 1;
a = a * a % p;
}
return ans;
}
ll inv(ll a,ll p){
return pow(a,p-2,p);
}
void getans(ll n,ll k){
ll ans = pow(2,n,mod)-1;
ll sum = 1;
for(ll i=1;i<k;i++){
sum = ( (sum * (n-i+1) % mod) * inv(i,mod)) % mod;
ans = (ans - sum + mod) % mod;
}
cout<<ans<<endl;
}
int main(){
ll t;
cin>>t;
for(ll i=1;i<=t;i++){
ll n,k;
cin>>n>>k;
printf("Case #%lld: ",i);
getans(n,k);
}
return 0;
}