题解 P2523 【[HAOI2011]Problem c】

Log_x · 2018-02-08 17:15:27 · 题解

Solution

• 先考虑无解的情况，我们记 s[i] 表示已经确定的 m 人中编号 \ge i 的人数。
• 那么如果存在 s[i] > n - i + 1，显然无解。
• 进一步的，对于有解的情况我们可以想到一个状态 f[i][j]，表示剩余 n - m 人中编号 \ge i的人已经确定 j 个人的编号的方案数，则：f[i][j] = \sum \limits_{k = 0}^j f[i + 1][j - k] \times C_j^k (0 \le j \le n - s[i] - i + 1)
• 即表示在已经确定 j - k 人编号的情况下，再选择 k 人确定编号为 i。
• 因为每个人都是互不相同的个体，所以对于任意一种方案，交换一些人的编号也算作不同的方案，因此还有乘上 C_j^k，表示 j 个人任选 k 人确定编号为 i。
• 答案即为 f[1][n - m]，时间复杂度 O(Tn^3)。

Code

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

namespace inout
{
    const int S = 1 << 20;
    char frd[S], *ihed = frd + S;
    const char *ital = ihed;

    inline char inChar()
    {
        if (ihed == ital)
            fread(frd, 1, S, stdin), ihed = frd;
        return *ihed++;
    }

    inline int get()
    {
        char ch; int res = 0; bool flag = false;
        while (!isdigit(ch = inChar()) && ch != '-');
        (ch == '-' ? flag = true : res = ch ^ 48);
        while (isdigit(ch = inChar()))
            res = res * 10 + ch - 48;
        return flag ? -res : res; 
    }
};
using namespace inout;

typedef long long ll;
const int N = 305;
int f[N][N], sum[N], c[N][N];
int n, m, T, Mod, x; 

int main()
{   
//  freopen("c.in", "r", stdin);
//  freopen("c.out", "w", stdout);

    T = get();
    while (T--)
    {
        memset(sum, 0, sizeof(sum));
        memset(f, 0, sizeof(f));

        n = get(); m = get(); Mod = get();
        for (int i = 1; i <= m; ++i)
            x = get(), ++sum[get()];

        bool flag = false;
        for (int i = n; i; --i)
        {
            sum[i] += sum[i + 1];
            if (sum[i] > n - i + 1) 
            {
                flag = true;
                break;
            }
        }
        if (flag)
        {
            puts("NO");
            continue;
        }

        for (int i = 0; i <= n; ++i) c[i][0] = 1;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= i; ++j)
                c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % Mod;

        f[n + 1][0] = 1;
        for (int i = n; i; --i)
            for (int j = 0, jm = n - sum[i] - i + 1; j <= jm; ++j)
                for (int k = 0; k <= j; ++k)
                    f[i][j] = ((ll)f[i][j] + (ll)f[i + 1][j - k] * c[j][k]) % Mod;
        printf("YES %d\n", f[1][n - m]); 
    }

//  fclose(stdin); fclose(stdout);
    return 0;
}