自动搬运

查看原文

来自洛谷，原作者为

	Log_x **

搬运于2025-08-24 21:38:38，当前版本为作者最后更新于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;
}