SRM459 Div1 Medium

500
まず、各マスに入る数字の重みを計算する。
次に、重みを足してtopを作るパターンを数える。
数え上げるdpで、for(各重み)for(和)と間違って、for(和)for(各重み)でやると、重複して数えてしまう。
間違えに気付くまで意外と時間をくった・・・。

class NumberPyramids {
public:
  int count(int baseLength, int top) {

    const int mod = 1000000009;

    const int N = 1000000+1;
    int t[N];
    fill( t, t + N, 1 );

    for(int i=0; i<baseLength; ++i){
      for(int j=1; j+i+1<baseLength; ++j){
        t[j] += t[j-1];
        if( top <= t[j] )return 0;
        if( t[j] <= 0 )return 0;
      }
    }

    for(int i=0; i<baseLength; ++i) cout << t[i] << ' '; cout << endl;


    lli sum = 0;
    for(int i=0; i<baseLength; ++i){
      sum += (lli)t[i];
    }
    if( (lli)top < sum )return 0;


    const int M = top + 1;
    int dp[M];
    fill( dp, dp + M, 0 ); dp[sum] = 1;

    for(int i=0; i<baseLength; ++i){
      for(int j=0; j<M; ++j){
        if( j + t[i] < M ){
          dp[j + t[i]] += dp[j];
          dp[j + t[i]] %= mod;
        }
      }
    }

    return dp[top];
  }
};