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());
    }
}

Download