题解：P14364 [CSP-S 2025] 员工招聘 / employ（民间数据）

前言

差点场切，写篇题解纪念一下。

Upd：修了一些锅。

思路

首先我们发现，若最后有

j

个人没有选上，那么

c_i>j

的所有位置可以随便乱排，也就是说我们只需要关心

c_i\le j

的位置。

所以就可以设状态

f_{i,j,k}

表示前

i

天，

j

个人没选上，有

k

个位置满足

c_i\le j

。

设

ton_i

表示

c_x=i

的个数，

pre_i

表示

ton_{0\sim i}

的和。转移考虑分类讨论：

$s_{i+1}=1$ $s_{i + 1} = 1$ ：
- 若当前这一位选上，填的数一定大于 $j$ ，所以 $f_{i,j,k}\to f_{i+1,j,k}$ ；
- 否则， $j$ 就会加一，填的数也一定小于等于 $j$ ，所以 $k$ 也要加一，此时我们需要枚举前 $i$ 天中等于 $j+1$ 的个数 $x$ ，那么转移即为 $f_{i,j,k} \binom{ton_{j+1}}{x}\binom{i-k}{x}x!(pre_{j}-k)\to f_{i+1,j+1,k+x+1}$ 。
$s_{i+1}=0$ $s_{i + 1} = 0$ ：无论如何一定不会选上，我们只需要考虑填的数和 $j+1$ $j + 1$ 的关系，以及前 $i$ $i$ 天中等于 $j+1$ $j + 1$ 的个数 $x$ $x$ 。
- 小于等于 $j+1$ ，转移为 $f_{i,j,k}\binom{ton_{j+1}}{x}\binom{i-k}{x}x!(pre_{j+1}-k-x)\to f_{i+1,j+1,k+x+1}$ ；
- 否则，转移为 $f_{i,j,k}\binom{ton_{j+1}}{x}\binom{i-k}{x}x!\to f_{i+1,j+1,k+x}$ 。

考虑如何计算答案，发现最后我们只需要让

k=pre_j

，然后在乘上剩下的数的填法，即

(n-pre_j)!

。

分析一下复杂度，由于

x

一定小于等于

ton_{j+1}

，总和是

O(n)

的，所以时间复杂度可以被分析到

O(n^3)

。

代码

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 505,mod = 998244353;
int n,m,ton[N],pre[N],a[N][N],c[N][N],f[2][N][N],fac[N];
string s;
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>s;
	for(int i = 1,x;i<=n;i++)
		cin>>x,ton[x]++;
	pre[0] = ton[0];
	for(int i = 1;i<=n;i++)
		pre[i] = pre[i-1]+ton[i];
	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;
	}
	a[0][0] = 1;
	for(int i = 1;i<=n;i++)
	{
		int now = 1;
		for(int j = 0;j<=i;j++)
		{
			a[i][j] = now;
			now = now*(i-j)%mod;
		}
	}
	fac[0] = 1;
	for(int i = 1;i<=n;i++)
		fac[i] = fac[i-1]*i%mod; 
	f[0][0][0] = 1;
	for(int i = 0;i<n;i++)
	{
		int now = (i&1);
		for(int j = 0;j<=n;j++)
			for(int k = 0;k<=n;k++)
			{
				if(!f[now][j][k]) continue;
				if(s[i]=='1')
				{
					(f[now^1][j][k]+=f[now][j][k])%=mod;
					for(int x = 0;x<=min(i-k,ton[j+1]);x++)
						(f[now^1][j+1][k+x+1]+=f[now][j][k]*c[ton[j+1]][x]%mod*a[i-k][x]%mod*(pre[j]-k))%=mod;
				}
				else
				{
					for(int x = 0;x<=min(i-k,ton[j+1]);x++)
					{
						(f[now^1][j+1][k+x]+=f[now][j][k]*c[ton[j+1]][x]%mod*a[i-k][x]%mod)%=mod;
						(f[now^1][j+1][k+x+1]+=f[now][j][k]*c[ton[j+1]][x]%mod*a[i-k][x]%mod*(pre[j+1]-k-x))%=mod;
					}
				}
				f[now][j][k] = 0;
			}
	}
	int ans = 0;
	for(int i = 0;i<=n-m;i++)
		(ans+=f[n&1][i][pre[i]]*fac[n-pre[i]])%=mod;
	cout<<ans;
	return 0;
}

题解：P14364 [CSP-S 2025] 员工招聘 / employ（民间数据）

文章操作

前言

思路

代码

相关推荐

评论

题解：P14364 [CSP-S 2025] 员工招聘 / employ（民间数据）