ARC162E Strange Constraints 做题记录

给定长度为 $n$ 的序列 $A$，求满足以下条件的序列 $B$ 的个数模 $998244353$ 的结果：

• 值域 $[1, n]$；
• $i$ 的个数不超过 $A_i$；
• $B_i$ 的个数不超过 $A_i$；

$1 \le A_i\le n \le 500$。

刚开始想的是把 $A$ 从大到小排序，这样每个数的出现次数就由它最后一次出现的位置决定，设 $f_{i,j,k}$ 表示处理完前 $A_{[1,i]}$，一共填了 $j$ 个位置，一共填了 $k$ 种数的方案数，但是发现是 $O(n^4)$ 的。

看题解发现忽略了一个很重要的东西：调和级数 $\sum\limits_{i=1}^n O(\frac{n}{i})=O(n\ln n)$。

设 $d_i$ 表示 $i$ 的出现次数，观察 $d$ 需要满足什么性质：

• $d_i\le A_i$；
• 对于所有满足 $d_i\le A_j$ 的位置 $j$，$B_j$ 可以等于 $i$；

观察到 $\forall d_i<d_j$，$j$ 能放的位置 $i$ 都能放，即 $i$ 的决策包含 $j$。

那么设 $f_{i,j,k}$ 表示决定完 $d_x\in[i,n]$ 的 $x$，共放了 $j$ 种不同的数，消耗了 $k$ 个位置的答案。

转移直接枚举有多少个 $x$ 满足 $d_x=i$ 即可。

由于 $j$ 的上界是 $\frac{n}{i}$，$d_x=i$ 的 $x$ 的个数上界也是 $\frac{n}{i}$，所以时间复杂度为 $O(n\sum\limits_{i=1}^n\frac{n^2}{i^2})$，约为 $O(n^2\ln^3 n)$，代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int S=505,p=998244353;

int n,a[S];
int fra[S],inv[S],pinv[S][S],C[S][S],f[S][S][S];

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(int i=0;i<=n;i++)
	{
		fra[i]=i==0?1:1ll*i*fra[i-1]%p;
		C[i][0]=1;
		for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
	}
	inv[n]=qpow(fra[n],p-2);
	for(int i=n;i>=1;i--) inv[i-1]=1ll*inv[i]*i%p;
	for(int i=0;i<=n;i++)
	{
		pinv[i][0]=1;
		for(int j=1;j<=n;j++) pinv[i][j]=1ll*pinv[i][j-1]*inv[i]%p;
	}
	f[n+1][0][0]=1;
	for(int i=n,pp=n+1;i>=1;i--)
	{
		while(pp>1&&a[pp-1]>=i) pp--;
		int len=n-pp+1;
		for(int j=0;j<=n/i&&j<=len;j++)
		{
			for(int k=0;k<=n;k++)
			{
				for(int l=0;l<=j&&l<=n/i&&l<=k/i;l++)
				{
					int bse=1ll*C[len-j+l][l]*C[len-k+i*l][i*l]%p*fra[i*l]%p*pinv[i][l]%p;
					add(f[i][j][k],1ll*bse*f[i+1][j-l][k-i*l]%p);
				}
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++) add(ans,f[1][i][n]);
	printf("%d\n",ans);
	return 0;
}