LEM6 - BIRTHDAY
Tác giả: skyvn97
Ngôn ngữ: Java
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
public class Main {
public static void main(String args[]) {
InputStream inputStream=System.in;
OutputStream outputStream=System.out;
InputReader in=new InputReader(inputStream);
PrintWriter out=new PrintWriter(outputStream);
LEM6 solver=new LEM6();
solver.solve(in,out);
out.close();
}
}
class LEM6 {
public void solve(InputReader in,PrintWriter out) {
int n=in.nextInt();
int m=in.nextInt();
int s=0;
for (int i=0;i<m;i=i+1) s+=in.nextInt();
if (s+m-1>n) {
out.println(0);
return;
}
if (m==1) {
out.println(n-s+1);
return;
}
BigInteger[][] comb=new BigInteger[m+1][n+1];
for (int i=0;i<=m;i=i+1)
for (int j=0;j<=n;j=j+1) {
if (i>j) comb[i][j]=BigInteger.ZERO;
if (i==j) comb[i][j]=BigInteger.ONE;
if (i<j) {
if (i==0) comb[i][j]=BigInteger.ONE;
else comb[i][j]=comb[i][j-1].add(comb[i-1][j-1]);
}
}
BigInteger res=BigInteger.ZERO;
for (int x=m-1;x+s<=n;x=x+1) res=res.add(comb[m-2][x-1].multiply(BigInteger.valueOf(n-x-s+1)));
out.println(res.toString());
}
}
class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader=new BufferedReader(new InputStreamReader(stream),32768);
tokenizer=null;
}
public String next() {
while (tokenizer==null || !tokenizer.hasMoreTokens()) {
try {
tokenizer=new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
}