Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

P2523 [HAOI2011]Problem c

Posted on

纪念一下第一道想出来的组合$dp$。

mydcwfy一眼秒了，orz。

Solution

首先不考虑分配编号到人，先处理出对于目前剩下的空位可以填的编号种类，然后枚举每一个编号选多少个，由于如果选了后面的编号。前面可选的数量一定会减少，于是强令选择的编号必须单调递减，然后在剩下的人中组合数分配一下就好了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
#define PII pair<int, int>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
	res = 0; bool flag = 0;
	char c = getchar();
	while(c < '0' || '9' < c) {if(c == '-') flag = 1; c = getchar();}
	while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
	if(flag) res = -res; 
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
template <class T>
void write(T res)
{
	if(res < 0) putchar('-'), res = -res;
	if(res > 9) write(res / 10);
	putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while(*s) putchar(*s ++);}
template <class T, class ...ARC>
inline void write(T res, ARC ...com) { write(res), write(com...); } 
const int N = 305;
int n, m, mod, T;
int f[N][N];
int a[N], cnt[N];
int C[N][N];
inline void init()
{
    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 - 1] + C[i - 1][j]) % mod; 
}
inline void work()
{
    read(n, m, mod);
    init();
    memset(f, 0, sizeof(f));
    memset(a, 0, sizeof(a));
    memset(cnt, 0, sizeof(cnt));
    for(int i = 1, l, r;i <= m;i ++)
        read(l, r), a[r] ++;
    for(int i = 1;i < n;i ++)
        if(a[i] > 1) a[i + 1] += a[i] - 1, a[i] = 1;
    if(a[n] > 1) return puts("NO"), void();
    for(int i = n;i >= 1;i --)
    {
        if(a[i]) continue;
        cnt[i] ++;
    }
    for(int i = n;i >= 1;i --) cnt[i] += cnt[i + 1];
    f[n + 1][0] = 1;
    for(int i = n + 1;i >= 1;i --) // 倒数第几个
    {
        for(int j = 0;j <= n - m;j ++)
        {
            if(!f[i][j]) continue;
            for(int k = 0;k <= min(n - m - j, cnt[i] - j);k ++)
            {
                f[i - 1][j + k] = (f[i - 1][j + k] + 1ll * f[i][j] * C[n - m - j][k] % mod) % mod;
            }
        }
    }
    write('Y', 'E', 'S', ' ', f[0][n - m], '\n');
}
int main()
{
    read(T);
    while(T --) work();
    return 0;
}