BZOJ 2302 - [HAOI2011]Problem c

#数学 #动态规划 #计数
Published on 2017-01-19

题目地址

描述

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

分析

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

这个题的规则的等价形式是：「对于每个 i(1≤i≤n)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] 坐满了人（显然 k≤jk\le j），那么一定有 n−k+1n - k + 1 个人的标号大于等于 kk，算上这个人，就有 n−k+2n - k + 2 个人的标号大于等于 kk。显然「对于每个 i(1≤i≤n)i(1\le i\le n)，都有不少于 ii 个人的标号 ≤i\le i」的等价形式为「对于每个 i(1≤i≤n)i(1\le i\le n)，都有不多于 n−i+1n - i + 1 个人的标号 ≥i\ge i」，我们对于 kk 违反了 n−k+1n - k + 1 个人的人数限制，所以这个人不可能没有座位，这就证明了充分性。

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

dp(i,j)=∑0≤k≤jdp(i−1,j−k)⋅(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;
}
BZOJ 2226 - [Spoj 5971] LCMSum