「HAOI 2011」Problem c

题目大意：

若标号大于等于 $x$ 的个数大于 $n-x+1$，则方案不可行，更好看的形式是，若标号小于等于 $x$ 的个数大于等于 $x$，那么这个方案可行。

设 $f[i][j]$ 表示有 $j$ 个人的值在 $[1,i]$ 中的方案数，有

$$f[i][j]=\sum\limits_{0 \leq k \leq j}f[i-1][k]\binom{n-k}{j-k}$$

转移时去掉已确定的 $m$ 即可。

#include <cstdio>
#include <cstring>
 
const int N = 305;
int f[N][N], s[N], c[N][N];
 
int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
void get_c(int n, int xzy) {
    c[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            c[i][j] = (c[i-1][j-1] + c[i-1][j]) % xzy;
    }
}
 
int main() {
    int T = read();
    while (T--) {
        int n = read(), m = read(), xzy = read(), ok = 1;
        memset(s, 0, sizeof s);
        memset(f, 0, sizeof f);
        for (int i = 1; i <= m; ++i) read(), ++s[read()];
        for (int i = n, j = 0; i; --i)
            if ((j += s[i]) > n - i + 1) { ok = 0, puts("NO"); break; }
        if (!ok) continue;
        for (int i = 1; i <= n; ++i) s[i] += s[i-1];
        get_c(n, xzy), f[0][0] = 1;
        for (int i = 1; i <= n; ++i) { //区间[1,i]
            for (int j = i - s[i]; j <= n - m; ++j) { //有j个人的标号在区间[1,i]中
                for (int k = 0; k <= j; ++k) { //有k个人的标号在区间[1,i-1]中
                    f[i][j] = (f[i][j] + 1LL * f[i-1][k] * c[n-m-k][j-k]) % xzy;
                }
            }
        }
        printf("YES %d\n", f[n][n-m]);
    }
    return 0;
}