# QLK04 - EDITORIAL

Practice

Contest

Author: Pritish Priyatosh Nayak

Tester: Saytabrat Panda

Editorialist: Pritish Priyatosh Nayak

Easy

Combinatorics

# PROBLEM:

Basically , the problem reduces to find the number of ways to distribute G-\sum_{i=1}^n A_i identical objects into N labeled boxes.

# QUICK EXPLANATION:

Use Stars and bars technique to find the answer.

# EXPLANATION:

We can see that the question is an application of Stars and bars theorem to find Number of lower-bound integer sums.

Let leftover prizes be l = G-\sum_{i=1}^n A_i.

So basically, we have to calculate \binom{l + n - 1}{l}.

For each test case we can loop from 1 to l + n - 1 to get the required factorials to calculate the answer.
Then as 10^7+9 is a prime number , modular inverse of the factorials can be calculated by using Fermatâ€™s little theorem.
For those who donâ€™t know ,
Fermatâ€™s little theorem states that if mod is prime , then inverse of any number x less than the mod is equal to x^{mod-2}%mod.
And x^{mod-2} can be calculated using Binary Exponentiation.

# SOLUTIONS:

Setter's/Editorialist's Solution
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;

int fast_exp(int base, int exp,int mod) {
int res=1;
while(exp>0) {
if(exp%2==1) res=(res*base)%mod;
base=(base*base*1LL)%mod;
exp/=2;
}
return res%mod;
}

int32_t main()
{
int t;
cin>>t;
while(t--)
{
int n,g;
cin>>n>>g;

int a[n];
for(int i=0;i<n;i++)
cin>>a[i];

int sum=accumulate(a,a+n,0LL);
g=g-sum;

int A=1,B=1,C=1;

for(int i=2;i<=g+n-1;i++)A=(A*i)%mod;
for(int i=2;i<=g;i++)B=(B*i)%mod;
for(int i=2;i<=n-1;i++)C=(C*i)%mod;

B=fast_exp(B,mod-2,mod);
C=fast_exp(C,mod-2,mod);

int ans=((A*B)%mod*C)%mod;
cout<<ans<<'\n';
}
}

Tester's Solution
import java.util.*;import java.io.*;import java.math.*;

public class Main
{

public static void process()throws IOException
{
long N=ni(),G=ni(),total=0l,rem=0l,res=0l;

for(int i=1;i<=N;i++)
total+=nl();

rem=G-total;

res=mcomb(rem+N-1,N-1);
pn(res);
}

static PrintWriter out;
public static void main(String[]args)throws IOException
{
out = new PrintWriter(System.out);

long s = System.currentTimeMillis();
int t=1;
t=ni();
while(t-->0)
process();

out.flush();
System.err.println(System.currentTimeMillis()-s+"ms");
System.out.close();
}

static void pn(Object o){out.println(o);}
static void p(Object o){out.print(o);}
static void pni(Object o){out.println(o);System.out.flush();}
static int ni()throws IOException{return Integer.parseInt(sc.next());}
static long nl()throws IOException{return Long.parseLong(sc.next());}
static double nd()throws IOException{return Double.parseDouble(sc.next());}
static String nln()throws IOException{return sc.nextLine();}
static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
static boolean multipleTC=false;
static long mod=(long)1e9+7l;

static<T> void r_sort(T arr[],int n){
Random r = new Random();
for (int i = n-1; i > 0; i--){
int j = r.nextInt(i+1);

T temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Arrays.sort(arr);
}

static long mpow(long x, long n) {
if(n == 0)
return 1;
if(n % 2 == 0) {
long root = mpow(x, n / 2);
return root * root % mod;
}else {
return x * mpow(x, n - 1) % mod;
}
}

static long mcomb(long a, long b) {
if(b > a - b)
return mcomb(a, a - b);
long m = 1;
long d = 1;
long i;
for(i = 0; i < b; i++) {
m *= (a - i);
m %= mod;
d *= (i + 1);
d %= mod;
}
long ans = m * mpow(d, mod - 2) % mod;
return ans;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////

{
StringTokenizer st;

}

String next(){
while (st == null || !st.hasMoreElements())
{
try
{
}
catch (IOException  e)
{
e.printStackTrace();
}
}
return st.nextToken();
}

String nextLine() {
String str = "";
try{
}
catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}

1 Like