AOJ 0537 Bingo
更新久しぶりです()
この問題は読み替えがポイントらしいですがそれよりもその後に苦戦した系くずです
結局1~mから相異なるn^2個の数を和がsになるように取り出す時の場合の数を求めてやればいいですがTLEやらMLEやらするので配列のとり方とかを工夫してdpしましょう
以下ソース
#include<cstdio> #include<cstring> using namespace std; typedef long long ll; ll dp[3001][50]; int n,m,s; int main(){ while(scanf("%d %d %d", &n, &m, &s)){ if(!n && !m && !s) break; memset(dp,0,sizeof(dp)); dp[0][0] = 1; for (int i = 1; i <= m; i++){ for (int j = n * n; j >= 1; j--){ for (int k = 1; k <= s; k++){ if(k - i >= 0)dp[k][j] += dp[k - i][j - 1]; } } } printf("%lld\n", dp[s][n * n] % 100000); } return 0; }