题解：AT_abc461_f [ABC461F] Total Product is N
zifeiwoye
·
·
题解
DP 好题。
Problem
任意集合 A 满足 \prod_{i\in A} i=N。求：
|A|!\sum_{i\in A} i
Analize
我们发现这个可以枚举每一个因子的进行搜索。简单的估计一下，因子个数不超过 5000 个，|A| 小于 50。
注意到消去一个因子后还是这个数的其中一个因子，所以这个搜索是有范围的，接下来发现我们剩下所需要的和就是搜索的范围，我们就可以考虑 DP。同时在设计状态时还要增加一维作为前面选择的个数（因为还有计数的可能性）。
我们就可以这样写出来一个记忆化搜索，空间很明显的 MLE 了。
考虑优化，发现这样子记忆化搜索的本质是是一个背包，可以把前面选择的个数这一维压掉。
Solution
记 val_i 为排名为 i 的因子
$g_{j,k}$ 为元素和之和。
则有：
$$
f_{t,k}=\sum_{i\cdot j=t,val_{i}\cdot val_{j}=val_{t}}f_{j,k-1}\\
g_{t,k}=\sum_{i\cdot j=t,val_{i}\cdot val_{j}=val_{t}}g_{j,k-1}\cdot val_i
$$
采用因子递增的方式递推。
发现这个算法劣在了找 $val_{i}\cdot val_{j}=val_{t}$ 上预处理一下即可。
### Code
```cpp
#include<bits/stdc++.h>
using namespace std;
#ifdef ONLINE_JUDGE
#define inline __attribute__((always_inline))
#define debug(x)
#else
#define debug(x) cerr<<#x<<" = "<<x<<"\n";
#endif
#define int long long
const int MOD=998244353,MAXN=5005,MAXK=50;
int n,cnt,val[MAXN],fact[MAXK],nxt[MAXN][MAXN],dpn[MAXN][MAXK],dps[MAXN][MAXK],tmpn[MAXN][MAXK],tmps[MAXN][MAXK];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i*i<=n;i++)
{
if(n%i==0)
{
val[++cnt]=i;
if(i*i!=n)
{
val[++cnt]=n/i;
}
}
}
sort(val+1,val+cnt+1);
for(int i=1;i<=cnt;i++)
{
for(int j=1;j<=cnt;j++)
{
nxt[i][j]=-1;
if(n/val[i]<val[j])
{
continue;
}
int pp=val[i]*val[j];
if(n%pp!=0)
{
continue;
}
int pos=lower_bound(val+1,val+cnt+1,pp)-val;
if(pos<=cnt&&val[pos]==pp)
{
nxt[i][j]=pos;
}
}
}
dpn[1][0]=1;
dps[1][0]=0;
for(int i=2;i<=cnt;i++)
{
int modv=val[i]%MOD;
for(int j=1;j<=cnt;j++)
{
for(int k=0;k<MAXK-1;k++)
{
tmpn[j][k]=0;
tmps[j][k]=0;
}
}
for(int j=1;j<=cnt;j++)
{
int to=nxt[i][j];
if(to==-1)
{
continue;
}
for(int k=0;k<MAXK-1;k++)
{
if(dpn[j][k]==0)
{
continue;
}
tmpn[to][k+1]=(tmpn[to][k+1]+dpn[j][k])%MOD;
int add=(dps[j][k]+dpn[j][k]*modv)%MOD;
tmps[to][k+1]=(tmps[to][k+1]+add)%MOD;
}
}
for(int j=1;j<=cnt;j++)
{
for(int k=1;k<MAXK;k++)
{
dpn[j][k]=(dpn[j][k]+tmpn[j][k])%MOD;
dps[j][k]=(dps[j][k]+tmps[j][k])%MOD;
}
}
}
for(int k=MAXK-2;k>=1;k--)
{
dpn[cnt][k]=(dpn[cnt][k]+dpn[cnt][k-1])%MOD;
dps[cnt][k]=(dps[cnt][k]+dps[cnt][k-1]+dpn[cnt][k-1])%MOD;
}
fact[0]=1;
for(int i=1;i<MAXK;i++)
{
fact[i]=(fact[i-1]*i)%MOD;
}
int ans=0;
for(int k=1;k<MAXK;k++)
{
int cur=dps[cnt][k];
int sum=(cur*fact[k])%MOD;
ans=(ans+sum)%MOD;
}
cout<<ans;
return 0;
}
```````