http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2383
350なのに全然解けない…と思ったら誤読で悲しかったです。
でも誤読した問題も少しおもしろいので紹介したいと思います。
今までプレイした最高難易度と同じもしくは簡単な問題を解くことがT回以下だった場合の数を求めよ。
ex.
1 3 2と解いた場合は1回、1 2 3と解いた場合は0回、3 2 1や3 1 2と解いた場合は2回です。
うしろから見てdpすればO(N^2)です。
下は元の問題のACコードです。
int N, M; int A[MAX_N]; int S[MAX_N]; void solve() { cin >> N >> M; rep(i, 0, N) { int a; cin >> a; A[a]++; S[a]++; } C_init(N + 10); rep(i, 1, 100000 + 1) { S[i] += S[i - 1]; } ll res = 1; rep(i, 1, 100000 + 1) { if(A[i] != 0) { MUL(res, C(S[i - 1] - S[max(i - M - 1, 0)] + A[i], A[i]) * fac[A[i]] % mod); } } cout << res << "\n"; }