PROBLEM LINK:
Author: Pritish Priyatosh Nayak
Tester: Saytabrat Panda
Editorialist: Pritish Priyatosh Nayak
DIFFICULTY:
Easy
PREREQUISITES:
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;
//answer is (g+n-1)C(g) = (g+n-1)!/((g)!(n-1)!)
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 FastReader sc;
static PrintWriter out;
public static void main(String[]args)throws IOException
{
out = new PrintWriter(System.out);
sc=new FastReader();
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;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
static class FastReader
{
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next(){
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
String nextLine() {
String str = "";
try{
str = br.readLine();
}
catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}
