0537 - Bingo

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0537
ビンゴのマスは２次元だが、1次元の配列として考えることが出来る。
つまりこの問題は、
N×N個の整数を昇順（狭義単調増加）で持つ配列で、要素の和がSであるものを求めよ。ただし各要素はm以下。
という問題に変換される。
これは、足される個数が指定された部分和問題の解の組合せ数を求める問題といえる。
ナップサック問題をヒントに、ループを逆順に回したりしてできたシンプルなコードが以下。
ここで、
dp[使った数][和] = パターン数
である。
逆順で回すところとか正直適当にやったらできてしまったのでちゃんと理解できるようにしたい…

ちなみに、自分のメモによるとAOJ0154が類題。足される個数が指定されない分こちらのほうが簡単。

int dp[50][3001];
int main() {
  int n,m,s;
  while(cin >>n>>m>>s,n) {
    memset(dp,0,sizeof(dp));
    dp[0][0] = 1;
    for (int i=1; i<=m; ++i)
      for (int j=n*n; j>0; --j)
        for (int k=s; k>=i; --k)
          dp[j][k] = (dp[j][k] + dp[j-1][k-i])%100000;
    cout << dp[n*n][s] << endl;
  }
}