BZOJ 2302 - [HAOI2011]Problem c

Published on 2017-01-19

题目地址

描述

n(n300)n(n\le 300) 个人安排座位,先给每个人一个在 [1,n][1, n] 内的编号,设第 ii 个人的编号为 aia_i(不同人的编号可以相同),接着从第一个人开始,大家依次入座,第 ii 个人来了以后尝试坐到 aia_i,如果 aia_i 被占据了,就尝试 ai+1a_i+1ai+1a_i + 1 也被占据了的话就尝试 ai+2a_i + 2,......,如果一直尝试到第 nn 个都不行,该安排方案就不合法。然而有 m(mn)m(m\le n) 个人的编号已经确定(他们或许贿赂了你的上司),你只能安排剩下的人的编号,求有多少种合法的安排方案。由于答案可能很大,只需输出其除以 M(M109)M(M\le {10}^9) 后的余数即可。

分析

像这种具有复杂规则的计数题目,往往需要找到规则的一个简洁的等价形式。这样才能方便我们计数。

这个题的规则的等价形式是:「对于每个 i(1in)i(1\le i\le n),都有不少于 ii 个人的标号 i\le i」,我们尝试证明一下:

证明:先证必要性:考虑任何一个合法的安排方案,假设有一个 ii 满足有少于 ii 个人的标号小于 ii,那么前 ii 个座位至少一个空位置,所以 nn 个人中至少有一个人没有座位,这与合法的安排方案矛盾。这就证明了必要性。

再证充分性:对于任意一个人的编号为 jj,我们来证明他一定能有一个位置。不妨假设他没有位置(已经安排好了标号在他之前的人的位置),那就说明 [j,n][j, n] 中已经坐满了人,我们找到最小的 kk 满足 [k,n][k, n] 坐满了人(显然 kjk\le j),那么一定有 nk+1n - k + 1 个人的标号大于等于 kk,算上这个人,就有 nk+2n - k + 2 个人的标号大于等于 kk。显然「对于每个 i(1in)i(1\le i\le n),都有不少于 ii 个人的标号 i\le i」的等价形式为「对于每个 i(1in)i(1\le i\le n),都有不多于 ni+1n - i + 1 个人的标号 i\ge i」,我们对于 kk 违反了 nk+1n - k + 1 个人的人数限制,所以这个人不可能没有座位,这就证明了充分性。

剩下的就是一个 DP 计数问题了,首先去掉「被钦定编号的人」,如果 ii 位置之前有 sis_i 个被钦定的人,那么 ii 位置的限制变为人数不小于 isii - s_i。设 dp(i,j)dp(i, j) 为在前 ii 个位置放 jj 个人的方案数(满足所有位置的限制条件),那么方程很容易写出来:

dp(i,j)=0kjdp(i1,jk)(jk) dp(i, j) = \sum_{0\le k\le j} dp(i - 1, j - k) \cdot \binom j k

单组询问复杂度:O(n3)O(n^3)

代码

//  Created by Sengxian on 2017/01/18.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  BZOJ 2302 转化 + DP
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 300 + 3;
int n, m, MOD, place[MAX_N], s[MAX_N];
int c[MAX_N][MAX_N], f[MAX_N][MAX_N];

void prepare() {
    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]) % MOD;
    }

    for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + place[i];
}

void solve() {
    memset(f, 0, sizeof f);
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = max(0, i - s[i]); j <= n - m; ++j)
            for (int k = 0; k <= j; ++k)
                (f[i][j] += (ll)f[i - 1][j - k] * c[j][k] % MOD) %= MOD;

    printf("YES %d\n", f[n][n - m]);
}

int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    int caseNum = readInt();
    while (caseNum--) {
        n = readInt(), m = readInt(), MOD = readInt();

        memset(place, 0, sizeof place);

        for (int i = 0; i < m; ++i) {
            int a = readInt(), b = readInt();
            place[b]++;
        }

        prepare();
        bool flag = true;
        for (int i = 1; i <= n; ++i) if (n - m + s[i] < i) flag = false;
        if (!flag) puts("NO");
        else solve();
    }
    return 0;
}