OI题有三种从一般到特殊，从暴力到优化，换角度思考 −WerkeyTom_FTD 这道题让我认识到了从题目到充要条件的转换这种解题思路 这道题我们可以看出他的充要条件为 ∀j,∑ni=1[ai>=j]<=n−j+1 现在我们要求的便为满足这个条件的序列的合法方案数，这个东西就很好dp了 f[i][j] 表示>=i的a有j个的合法方案数, r[i] 表示被钦定为a(a=i)的人有多少个 m[i] 表示被钦定为a(a>i)的人有多少个 f[i][j]=∑j−r[i]k=0f[i+1][k]∗Cj−k−r[i]n−k−m[i]+l[j<=n−i+1]
#include<cstdio> #include<algorithm> #include<cstring> const int N = 310; int C[N][N], p[N], n, m, k, a1, a2, P, f[N][N], r[N]; void Solve () { memset (f, 0, sizeof f); scanf ("%d%d%d", &n, &m, &P); memset (C, 0, sizeof C); C[0][0] = 1; for (int i = 1; i <= 300; ++i) { C[i][0] = 1; for (int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P; } for (int i = 1; i <= n; ++i) p[i] = -1, r[i] = 0; for (int i = 1; i <= m; ++i) scanf ("%d%d", &a1, &a2), ++r[a2]; for (int i = n, l = 0; i; --i) { l += r[i]; if (n - i + 1 < l) { puts ("NO"); return ; } } f[n + 1][0] = 1; for (int i = n, l = 0; i; --i) { for (int j = l; j <= n - i + 1; ++j) for (int k = 0; k <= j - r[i]; ++k) f[i][j] = (f[i][j] + 1ll * f[i + 1][k] * C[n - k + l - m][j - k - r[i]] % P) % P; l += r[i]; } printf ("YES %d\n", f[1][n]); } int main () { int T; scanf ("%d", &T); while (T--) Solve (); return 0; }