「HAOI2011」Problem c

「HAOI2011」Problem c

传送门

由于这道题本人讲得不好，可以参考这位dalao的博客
我可就直接上代码了。。。

参考代码：

/*--------------------------------
  Code name: D.cpp
  Author: The Ace Bee
  This code is made by The Ace Bee
--------------------------------*/
#include <cstdio>
#include <cstring>
#define int long long 
#define rg register
#define file(x)                                     freopen(x".in", "r", stdin);                    freopen(x".out", "w", stdout);
const int $ = 333;
inline int read() {
    int s = 0; bool f = false; char c = getchar();
    while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = getchar();
    return f ? -s : s;
}
int n, m, mod;
int c[$][$], cnt[$], sum[$], f[$][$];
inline void getc() {
    c[0][0] = 1;
    for (rg int i = 1; i <= n; ++i) {
        c[i][0] = 1;
        for (rg int j = 1; j <= i; ++j)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    }
}
inline void plus(int& a, int b) { a = (a + b) % mod; }
signed main() {
//  file("D");
    for (rg int T = read(); T; --T) {
        memset(cnt, 0, sizeof cnt);
        memset(f, 0, sizeof f);
        n = read(), m = read(), mod = read();
        getc();
        for (rg int i = 1; i <= m; ++i) read(), ++cnt[read()];
        sum[0] = n - m;
        bool flag = true;
        for (rg int i = 1; i <= n; ++i) {
            sum[i] = 1ll * cnt[i] + 1ll * sum[i - 1];
            if (sum[i] < i) { flag = false; break; }
        }
        if (!flag) { puts("NO"); continue; }
        f[0][0] = 1;
        for (rg int i = 1; i <= n; ++i)
            for (rg int j = i; j <= sum[i]; ++j)
                for (rg int k = cnt[i]; j - k >= i - 1; ++k)
                    plus(f[i][j], 1ll * f[i - 1][j - k] * c[sum[i - 1] - j + k][k - cnt[i]]);
        printf("YES %lld\n", f[n][n]);
    }
    return 0;
}

「HAOI2011」Problem c

原文：https://www.cnblogs.com/zsbzsb/p/12246839.html