0537: Bingo | Aizu Online Judge

Bingo | Aizu Online Judge

状態数をうまく削減しないといけない。

int N, M, S;
int dp[50][3005];

int mod = 100000;

int main() {
    while (1) {
        cin >> N >> M >> S;
        if (N == 0) break;
        memset(dp, 0, sizeof(dp));
        N *= N;
        dp[0][0] = 1;
        for (int i = 1; i <= M; i++) {

            for (int j = N; j>0; j--){
                for(int k=i;k<=S;k++){
                    dp[j][k]=(dp[j][k]+dp[j-1][k-i])%mod;
                }
            }
        }
        printf("%d\n", dp[N][S]);
    }
    return 0;
}