POJ 3046 Ant Counting

問題（http://poj.org/problem?id=3046）

ラベル１〜T（11000）をつけたアリがA匹います。
各々のラベルをつけたアリは、匹（）です。
サイズがS〜Bの異なる集合は何種類あるでしょうか。

異なる集合を数え上げたいので、各々の集合は昇順に並べられているとします。
すると、最終要素の個数によって、サイズを一つ上げた時にすべき挙動が変わることになります。
具体的には、を「最終要素がラベルiで、j個含まれている集合の個数」とすると、
の時には、
となります。
また、k>iなるkを最終要素に加えることで、新たな集合を作ることもできるので、コードは以下のようになりました。

#include <cstdio>
#include <iostream>
#include <vector>
#include <map>

using namespace std;

#define MAX_T 1000
#define MAX_N 100
#define MAX_A 100000
#define BASE 1000000
int T, A, B, S;
int N[MAX_T];
int dp[2][MAX_T][MAX_N];

void solve(){
  int cnt = 0;
  for(int i=0; i<T; i++){
    dp[1][i][0] = 1;
    dp[0][i][0] = 0;

    for(int j=1; j<N[i]; j++){
      dp[0][i][j] = 0;
      dp[1][i][j] = 0;
    }
  }
  int size = 2;
  while(size <= B+1){
    int sum = 0;
    for(int i=0; i<T; i++){
      for(int j=0; j<N[i]; j++){
	if(dp[(size+1)%2][i][j] > 0){
	  if(j < N[i]){
	    dp[size%2][i][j+1] += dp[(size+1)%2][i][j];
	    dp[size%2][i][j+1] %= BASE;
	  }
	  sum += dp[(size+1)%2][i][j];
	  sum %= BASE;
	  if(size>S){
	    cnt += dp[(size+1)%2][i][j];
	    cnt %= BASE;
	  }
	  dp[(size+1)%2][i][j] = 0;
	}
      }
      if(i+1<T){
	dp[size%2][i+1][0]+=sum;
	dp[size%2][i+1][0] %= BASE;
      }
    }
    size++;
  }
  cout << cnt << endl;
}

int main(){
  fill(N, N+MAX_T, 0);
  scanf("%d %d %d %d", &T, &A, &S, &B);  
  int tmp;
  for(int i=0; i<A; i++){
    scanf("%d", &tmp);
    N[tmp-1]++;
  }
  solve();
  return 0;
}

まだまだ遅いので、もっと効率のやり方があるのだろうなと思います。