[BZOJ2392][HAOI2011]Problem c

Description

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

Input

第一行一个整数T，表示数据组数

对于每组数据，第一行有三个整数，分别表示n、m、M

若m不为0，则接下来一行有m对整数，p1、q1，p2、q2 ,…, pm、qm，其中第i对整数pi、qi表示第pi个人的编号必须为qi

Output

对于每组数据输出一行，若是有解则输出YES，后跟一个整数表示方案数mod M，注意，YES和数之间只有一个空格，否则输出NO

Sample Input

4 3 10

1 2 2 1 3 1

10 3 8882

7 9 2 9 5 10

Sample Output

YES 4

HINT

100%的数据满足：1≤T≤10，1≤n≤300，0≤m≤n，2≤M≤109，1≤pi、qi≤n 且保证pi互不相同。

还是考虑关于一个排列的的计数问题有两种基本的思路，一是考虑一个元素放在哪一个位置，二是考虑一个位置可以放哪些元素。

对于这道题用第二种思路比较好解决。

我们发现，问题有解的必要条件是在第$i$个位置，可以在$i$及之前放置的人的个数大于等于$i$。

所以我们维护前缀和$sum[i]$表示编号确定在$i$之前的人的个数，特别的如果一个人没有确定的编号，那么它的最小编号就是0，所以$sum[0]=n-m$。

设$cnt[i]$为编号必须是i的人的个数。

然后设$f[i][j]$表示前$i$个位置，已经安排完了$j$个人的方案数，显然$j>i$。

那么我们转移就是枚举$i$这个位置放$k$个人然后$f[i][j] = f[i][j]+f[i-1][j-k] \times C(sum[i]-(j-k)-cnt[i], k-cnt[i])$。

意思就是刨去必须在这个位置上选的数。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

#define reg register

inline int read() {

    int res = ;char ch=getchar();bool fu=;

    while(!isdigit(ch))fu|=(ch=='-'),ch=getchar();

    while(isdigit(ch))res=(res<<)+(res<<)+(ch^), ch=getchar();

    return fu?-res:res;

}

#define ll long long

int n, m, mod;

ll C[][];

ll f[][], cnt[], sum[];

bool ok;

int main()

{

    int T = read();

    while(T--)

    {

        n = read(), m = read(), mod = read();

        memset(f, , sizeof f), memset(C, , sizeof C);

        memset(cnt, , sizeof cnt), memset(sum, , sizeof sum);

        ok = ;

        C[][] = ;

        for (reg int i =  ; i <= n ; i ++)

        {

            C[i][] = ;

            for (reg int j =  ; j <= i ; j ++) C[i][j] = (C[i - ][j] + C[i - ][j - ]) % mod;

        }

        for (reg int i =  ; i <= m ; i ++) read(), cnt[read()]++;

        sum[] = n - m;

        for (reg int i =  ; i <= n ; i ++) sum[i] = sum[i - ] + cnt[i];

        for (reg int i =  ; i <= n ; i ++) if (sum[i] < i) {ok = ;break;}

        if (!ok) {puts("NO");continue;}

        f[][] = ;

        for (reg int i =  ; i <= n ; i ++)

            for (reg int j = i ; j <= sum[i] ; j ++)

                for (reg int k = cnt[i] ; j - k >= i -  ; k ++)

                    f[i][j] = (f[i][j] + f[i - ][j - k] * C[sum[i] - (j - k) - cnt[i]][k - cnt[i]]) % mod;

        printf("YES %lld\n", f[n][n]);

    }

    return ;

}

巴特西