[ARC116C] Multiple Sequences题解

思路

我们可以很好的想到一种 \(O(nm)\) 的 dp:

状态：\(dp_{i,j}\) 为搜到第 \(i\) 个,最后一个数是 \(j\) 的方案数。

转移：\(dp_{i,j} = \displaystyle\sum_{k|j,k\not =j}dp_{i-1,k}\)

当然这是会超时的。

我们换一种思路，我们先枚举最后一个数，再计算方案数。

这有个好处，我们缩小了前面的数的范围，必定是最后一个数的因数。

我们先分解最后一个数的质因数，统计每个质因数的指数，质因数不超过 \(6\) 个。

然后我们将质因数分配给前面的数，这里的分配是指：假设我分配了 \(2\) 给一个数，则这个数是前面的一个数乘 \(2\)。

这样避免了前面的数不满足条件。

将质因数分配给前面的数，相当于 \(n\) 个小球,放进 \(m\) 个盒子里，可以留空。

也就是 \(\tbinom{m-1}{n+m-1}\) 。

最后将答案统计起来就好了

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+100,Mod=998244353;
int n,m,ans;
int fac[N+10],inv[N+10];
int qpow(int a,int b)
{
	int res=1;
	for(;b;a=a*a%Mod,b>>=1)
		if(b&1)res=res*a%Mod;
	return res;
}
int C(int n,int m){return n==m||m==0?1:fac[n]*inv[n-m]%Mod*inv[m]%Mod;}
signed main()
{
	scanf("%lld%lld",&n,&m);
	fac[1]=1ll;
	for(int i=2;i<=N;i++)fac[i]=fac[i-1]*i%Mod;
	inv[N]=qpow(fac[N],Mod-2);
	for(int i=N-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%Mod;
	for(int i=1;i<=m;i++)
	{
		int temp=i,tmp=1;
		for(int j=2,cnt=0;j*j<=temp;j++)
		{
			cnt=0;
			while(temp%j==0)cnt++,temp/=j;
			tmp=tmp*C(cnt+n-1,n-1)%Mod;
		}
		if(temp!=1)tmp=tmp*n%Mod;
		ans+=tmp,ans%=Mod;
	}
	cout<<ans;
}