[ARC116C] Multiple Sequences题解

random_0708 · 2023-10-03 11:04:09 · 题解

思路

我们可以很好的想到一种 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;
}