思路

题目要求求可重集合的数量，我们不妨从正常集合入手。

如果要求集合的数量，不难发现其实答案就是$k$，因为每次操作你可以选择从$0$开始的连续自然数，直到黑板上没有这个数，最后再黑板上写下新的数；或者是写上一个以前出现过的数。最后的答案数就是最多可以写下的新数的数量，即$k$。

我们接着从这种情况衍生到题目要求的情况。

对于可重集合，我们只需对于写下$i$种新数的情况统计它剩余的操作次数可以写下那些写过的数。这里可以用排列组合来计算，计算方法如下：对于所有的$1$到$i$数都要写到黑板上，写了$cnt$个新数的情况对答案的贡献即为$C^{i}_{K-cnt+i}$。（具体解释见题解末）

AC代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e5+10,P=998244353;
int a[N],f[N+N],n,k;
bool v[N+N];
int qpow(int a,int b)
{
	int res=1;
	for(;b;b>>=1,a=a*a%P)if(b&1)res=res*a%P;
	return res;
}
int c(int x,int y)
{
	return f[x]*qpow(f[x-y],P-2)%P*qpow(f[y],P-2)%P;
}
signed main()
{
	scanf("%lld%lld",&n,&k);
	f[0]=1;for(int i=1;i<=n+k;i++)f[i]=f[i-1]*i%P;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		v[a[i]]=1;
	}
	int ans=0;
	for(int i=0,cnt=0;i<=n+k;i++)
	{
		if(!v[i])cnt++;
		if(v[i+1])continue;
		if(cnt>k)break;
		ans=(ans+c(k-cnt+i,i))%P;
	}
	printf("%lld\n",ans);
	return 0;
}

为什么是$C_{K-cnt+i}^i$？

这个公式代表将$K-cnt$个数分配到$i+1$个集合中，相当于是将$K-cnt$个多余操作分配到$i+1$个数上，即$0$到$i$，具体原因见OIWIKI

这是本蒟蒻第一次写数学相关的题解，写的不好的地方欢迎巨佬提建议^v^