对于任意一个multiset，我们都把它的元素从大到小排序来观察。发现一个multiset合法有个必要条件：对于每个i，multiset中最大的i个元素之和不能超过\(lim_i\)，如果令\(c_i\)表示输入的数中i出现的次数，则\(lim_i=\sum_{j=1}^n min(i,c_j)\)。根据题意，很容易发现不符合这个条件的multiset一定是不合法的。
其实这个条件也是充分的。证明也不难，假设一个合法的multiset中有某两个数，一大一小，那么肯定可以从大的那个数中拿出1，加到小的里面，使得multiset仍然合法，我们称这个操作为"调整"。根据题意，一定存在一个合法的multiset满足对于所有i，这个multiset中最大的i个数之和=\(lim_i\)，也就是刚好卡着所有限制。那么所有满足上面条件的multiset一定能由这个卡着所有限制的multiset调整而来，所以它们全部合法。
接下来就是对满足这个条件的multiset计数了。先把所有的\(lim_i\)计算出来，时间复杂度\(O(n^2)\)。从大往小向multiset中填数，令\(dp_{i,j,k}\)表示填了i个数，当前所有数的和是j，其中第i个数的值为k的方案数。接下来填的数不能大于k，且所有数的和不能超过\(lim_{i+1}\)。发现对于固定的i，只有\(k \le \lfloor \frac ni \rfloor\)的状态才是合法的，所以合法状态总数是\(O(n^2logn)\)的。把i这一维滚动掉就可以做到\(n^2\)的空间复杂度。转移可以用前缀和优化到\(O(1)\)。
总时间复杂度\(O(n^2logn)\)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nPROGRAM TERMINATED";
#endif
exit(0);
}
using namespace std;
const LL MOD=998244353;
LL n,a[2010],cnt[2010],lim[2010],dp[2][2010][2010];
int main()
{
fileio();
cin>>n;
rep(i,n)
{
cin>>a[i];
++cnt[a[i]];
}
repn(i,n) repn(j,n) lim[i]+=(cnt[j]<=i ? cnt[j]:i);
dp[0][0][n]=1;
rep(ii,n)
{
int i=ii&1,kmx=(ii==0 ? n:n/ii);
rep(j,n+1)
{
LL val=0;
for(int k=kmx;k>=0;--k)
{
(val+=dp[i][j][k])%=MOD;
if(j+k<=lim[ii+1]) (dp[i^1][j+k][k]+=val)%=MOD;
dp[i][j][k]=0;
}
}
}
LL ans=0;
rep(i,n+1) (ans+=dp[n&1][n][i])%=MOD;
cout<<ans<<endl;
termin();
}