Ant Counting (POJ 3046)

This problem is equal to given several types of objects and their count and ask how many different combinations you can get by picking K out of them.

Let $DP[i][j]$ denotes how many ways we can pick $j$ objects from the first $i$ types of objects. Then we have:

$$DP[i+1][j] = \sum_{k = 0}^{\min(j, c_i)} DP[i][j - k]$$

But this formular cost $O(NC)$ time to process which is to cost. We have to optimize the formular to

$$DP[i+1][j]=\begin{cases} DP[i+1][j-1]+DP[i][j]+DP[i][j-1-c_{i}] & \; j-1-c_{i}\ge0\\ DP[i+1][j-1]+DP[i][j] & otherwise \end{cases}$$

Then the time cost reduced to $O(N)$ and is acceptable now.

import java.io.*;
import java.util.*;

public class AntCounting {
    static private int MOD = 1000000;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt(), A = in.nextInt(), S = in.nextInt(), B = in.nextInt();
        int[] count = new int[T];
        for (int a = 0; a < A; a++) {
            count[in.nextInt() - 1]++;
        }
        int[] dp = new int[B + 1];
        int[] last = new int[B + 1];
        dp[0] = last[0] = 1;
        for (int i = 0; i < T; i++) {
            int c = count[i];
            for (int j = 1; j <= B; j++) {
                dp[j] = (dp[j - 1] + last[j] - (j - c - 1 >= 0 ? last[j - c - 1] : 0) + MOD) % MOD;
            }
            int[]tmp = dp;
            dp = last;
            last = tmp;
        }
        int sum = 0;
        for (int i = S; i <= B; i++) {
            sum = (sum + last[i]) % MOD;
        }
        System.out.println(sum);
    }
}