我要水题解

· · 题解

首先通过观察得出数据范围内一个数最多只有 2304 个因数，优美序列的长度最多为 13。那大概就是需要 O(d(n)^2 k) 的做法。

考虑 dp。

先默认该序列单调递增，最后对于不同长度的贡献再乘上 k!。

因为乘积肯定为 n 的因数，所以只需记录状态乘积为第几大的因数。再记录得到这个乘积使用了多少个数。再使用两个 dp 数组，一个解决方案数，一个解决序列和。

每次类似背包的从小到大把一个个因数加上去算贡献，实现如下式，dp 维护和，f 维护方案数，mp 是开个哈希表维护该因数的排名。

f[j][k] \leftarrow f[j][k] + f[p][k-1] \\[6pt] dp[j][k] \leftarrow dp[j][k] + dp[p][k-1] + a[i] \cdot f[p][k-1] \end{cases} \quad \text{其中 } p = \operatorname{mp}\!\bigl(a[j] / a[i]\bigr),\ a[j] \bmod a[i] = 0

然后写代码即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int P=998244353;
int n,dp[3000][15],f[3000][15],a[3000],g[15],len,ans;
unordered_map < int , int > mp;
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    g[0]=1;
    for (int i=1;i<=13;i++) g[i]=g[i-1]*i%P;
    for (int i=1;i*i<=n;i++){
        if (n%i==0){
            a[++len]=i;
            if (i*i!=n) a[++len]=n/i;
        }
    }
    sort(a+1,a+len+1);
    for (int i=1;i<=len;i++) mp[a[i]]=i;
    f[1][0]=1;
    for (int i=1;i<=len;i++){
        for (int k=13;k;k--){
            for (int j=i;j<=len;j++){
                if (a[j]%a[i]!=0) continue;
                f[j][k]=(f[j][k]+f[mp[a[j]/a[i]]][k-1])%P;
                dp[j][k]=(dp[j][k]+dp[mp[a[j]/a[i]]][k-1]+a[i]*f[mp[a[j]/a[i]]][k-1]%P)%P;
            }           
}
    }
    for (int k=1;k<=13;k++) ans=(ans+g[k]*dp[len][k]%P)%P;
    cout<<ans;
    return 0;
}