LEM6 - BIRTHDAY

Tags: bignum, math

Problem

https://vn.spoj.com/problems/LEM6

https://oj.vnoi.info/problem/LEM6

Chỉ năm nay nữa thôi là sherry sẽ tốt nghiệp Đại Học rồi vì thế sherry muốn sinh nhật năm nay của mình sẽ thật ý nghĩa. Và Sherry mời tất cả bạn của mình đến dự sinh nhật ^^

Sherry tổ chức 1 trò chơi nhỏ cho tất cả các bạn cùng tham gia, sherry có 1 tờ giấy HCN kích thước 1 x N và M mảnh nhỏ hơn, mảnh giấy thứ i có kích thước 1 x Ai. bây giờ sherry đố các bạn của mình có bao nhiêu cách đặt các mảnh giấy nhỏ theo thứ tự từ 1 đến M vào mảnh giấy 1 x N sao cho mỗi mảnh giấy cách nhau ít nhất 1 ô vuông ( Nếu i < j thì mảnh giấy thứ i sẽ được đặt nằm trước mảnh giấy thứ j ). Sherry hứa sẽ tặng 1 món quà đặc biệt cho bạn nào trả lời nhanh nhất :D

Input

Dòng 1: N, M ( 1 <= N <= 1000, 1 <= M <= N/2 )

Dòng 2: Gồm M số, số thứ i là Ai

Output

Gồm 1 dòng duy nhất là số cách tìm được

Example

Input
4 2
1 1
Output
3

Tutorial


Submission

LEM6.java
import java.io.*;
import java.util.*;
import java.lang.*;
import java.math.*;
import java.text.*;
 
 
public class Main {
    
    public static Scanner cin = new Scanner(System.in);
    
    public static void main(String[] args) throws IOException  {
        
        /*
        FileInputStream fi = new FileInputStream("D:/java.inp"); 
        Scanner in = new Scanner(fi);
        FileOutputStream fo = new FileOutputStream("D:/java.out");
        PrintWriter out = new PrintWriter(fo);
        */
        
        //BufferedReader in = new BufferedReader(new FileReader(new File("D:/java.inp")));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        
        DecimalFormat df = new DecimalFormat("#.000"); 
        
        //------------------------------------------------------------------------------//
        
        String s[] = in.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        String t[] = in.readLine().split(" ");
        int S = 0;
        for (int i=0;i<m;i++) {
        	int x = Integer.parseInt(t[i]);
        	S += x;
        }
        if (n < S+m-1) {
        	System.out.println("0");
        	return;
        }
        BigInteger c[][] = new BigInteger[n+5][n+5];
        for (int j=0;j<=n-S+1;j++) 
        	for (int i=0;i<=j;i++) c[i][j] = BigInteger.valueOf(0);
        
        for (int j=0;j<=n-S+1;j++) {
        	for (int i=0;i<=j;i++) {
        		if (i == 0 || i == j) {
        			c[i][j] = BigInteger.valueOf(1);
        		}
        		else {
        			c[i][j] = c[i][j-1].add(c[i-1][j-1]);
        		}
        	}
        }
        
        System.out.println(c[m][n-S+1]);
    }
    
    
}