AT_abc461_f 题解

· · 题解

做不了一点。

前面这个工单说这题是黄的（看我评论），我去，这对吗？？黄？？？吓哭了，你说 D 是黄我认，你说 E 是黄我认，你告诉我这个 F 是黄？

喵的。

首先肯定要分解因数啊，把 n 的所有因数找出来存在 d 数组里（设一共有 m 个），排序后对其编号方便后续定义 DP 状态和转移 DP。时间复杂度 O(\sqrt{n})。

定义 dp_{i,j} 表示当前分配的值的总乘积为 i（一定是 n 的因数，用 d 中编号记录）且总共分配了 j 个值时的和，g_{i,j} 表示同样状态下的总分配方案数。

初始化 dp_{1,0} = 0 但 g_{1,0} = 1 也就是什么都还没有的状态。类似背包，枚举新增因子 i、原先因子 k 和原先数量 j，只要 i \times k 还是 n 的因数（如果不是了的话就不再可能累加到 n 了）就可以转移，从 dp_{k,j} 转移到 dp_{ik,j+1}（扩散型）。具体地，让 dp_{ik,j+1} \gets dp_{ik,j+1} + ( dp_{k,j} + g_{k,j} i ) 且 g_{ik,j+1} \gets g_{ik,j+1} + g_{k,j} 即可。记得对 998244353 取模。

最后的答案是多少呢？题目没有限制序列长度，所以是所有 \sum dp_{n,x} 吗？当然不是！这里的 dp 数组是按照选取组合来算的，而题目要求的是排列，所以答案是 \sum (dp_{n,x} \times x!)。

最终时间复杂度是 O(\sqrt n + d(n)^2 B)，其中 d(n) 表示 n 的因数个数，B 表示序列的最长长度（取 14 即可，因为 14! > 10^{10} \ge n）。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2500;
const LL MOD = 998244353;
LL n,m,d[N];
LL dp[N][20],g[N][20];
LL Ans,fac[20];
map<LL,int> mp;
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
inline void upd(LL &x,LL y){x=(x+y)%MOD;return;}
int main(){
    n=read(),m=0;
    for(LL x=1;x*x<=n;x++)
        if(n%x==0){
            d[++m]=x;
            if(n/x!=x)d[++m]=n/x;
        }
    sort(d+1,d+m+1);
    for(int i=1;i<=m;i++)mp[d[i]]=i;
    g[mp[1]][0]=1;
    for(int i=1;i<=m;i++)
        for(int j=13;j>=0;j--)
            for(int k=1;k<=m;k++){
                if(!dp[k][j]&&!g[k][j])continue;
                if(!mp.count(d[k]*d[i]))continue;
                int nxt=mp[d[k]*d[i]];
                upd(dp[nxt][j+1],dp[k][j]+g[k][j]*d[i]);
                upd(g[nxt][j+1],g[k][j]);
            }
    fac[0]=1;
    for(int x=1;x<=14;x++)fac[x]=fac[x-1]*x%MOD;
    for(int x=1;x<=14;x++)
        upd(Ans,dp[m][x]*fac[x]%MOD);
    cout<<Ans<<"\n";
    return 0;
}

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！