競プロやっているomochanという人です。適当に解いた問題を載せていくのでよろしくお願いします。
JOI Kangaroo
int N; ll dp[2][MAX_N][MAX_N]; pi P[MAX_N]; int C[MAX_N]; bool bigger(const pi& p1, const pi& p2) { return p1.second < p2.second; } void solve() { cin >> N; rep(i, 0, N) { int a, b; cin >> a >> b; P[i] = make_pair(a, b); } sort(P, P + N, bigger); rep(i, 0, N) { int c1 = 0, c2 = 0; int a1 = (i == 0 ? 0 : P[i - 1].sec), a2 = P[i].sec; rep(j, 0, i) { if(P[j].fst < a2) c2++; if(P[j].fst < a1) c1++; } C[i] = c2 - c1; } dp[0][0][0] = 1; int pre, nex; rep(i, 0, N) { pre = i % 2; nex = 1 - i % 2; rep(j, 0, N + 1) rep(k, 0, N + 1) dp[nex][j][k] = 0; rep(j, 0, N) { rep(k, 0, N) { if(k - C[i] >= 0) { ADD(dp[nex][j][k], dp[pre][j + 1][k - C[i]] * (j + 1)); } if(k - C[i] + 1 >= 0) { ADD(dp[nex][j][k], dp[pre][j][k - C[i] + 1] * (k + 1)); } } rep(k, 0, j - C[i] + 1) { ADD(dp[nex][j][0], dp[pre][j - C[i] - k][k]); } } } ll res = 0; rep(i, 0, N) ADD(res, dp[nex][0][i]); cout << res << '\n'; }