题解：AT_abc461_f [ABC461F] Total Product is N

· · 题解

压哨翻盘这一块，毙完作弊 perf 起飞这一块。

查表可知因数数量不超过 d=2304。

考虑 dp，具体的，我们定义 dp_{i,j,k} 表示决策到第 i 个因子，已经选定了 j 个因子，得到的乘积是 k 的方案数。注意这里并不要求序列的顺序。

我们每次转移暴力枚举 j 和 k 就可以了，注意到 k 也是 n 的因子，所以时间复杂度是 O(d^2\log n) 的。

注意我们需要维护的是和而不是方案数，但是在转移和的时候对于前面的每个方案当前数字转移过来都会产生贡献，所以是需要维护方案数的。

这两个都是很简单的 dp 就可以解决的，只要不写挂就可以了。

最后对于每个贡献，我们都需要乘上选择的数字数量的阶乘，这就是为什么设计状态的时候需要保留一个长度维的原因。

做完了。

vector<int>ve;
int A[40];
int dp[2][40][2505];
int sm[2][40][2505];
map<int,int>mp;
inline void solve(){
    int n;
    cin>>n;
    ve.push_back(-1);
    int tp=0;
    for(int i=1;i*i<=n;i++)
    if(n%i==0){
        ve.push_back(i);
        mp[i]=++tp;
        if(i*i!=n)
        ve.push_back(n/i),
        mp[n/i]=++tp;
    }
    int m=ve.size()-1;
    dp[0][0][1]=1;
    for(int i=1;i<=m;i++){
        for(int j=0;j<=m;j++)
        for(int k=0;k<40;k++)
        dp[i&1][k][j]=dp[(i&1)^1][k][j],
        sm[i&1][k][j]=sm[(i&1)^1][k][j];
        for(int j=1;j<=m;j++){
            for(int k=1;k<40;k++)
            if((ve[i]<=sqrt(n)||ve[j]<=sqrt(n))&&n%(ve[i]*ve[j])==0)
            dp[i&1][k][mp[ve[i]*ve[j]]]+=dp[(i&1)^1][k-1][j],
            sm[i&1][k][mp[ve[i]*ve[j]]]+=(sm[(i&1)^1][k-1][j]+
                        ve[i]%mod*dp[(i&1)^1][k-1][j]%mod)%mod,
            sm[i&1][k][mp[ve[i]*ve[j]]]%=mod,
            dp[i&1][k][mp[ve[i]*ve[j]]]%=mod;
        }
    }
    int ret=0;
    for(int i=1;i<40;i++)
    ret=(ret+sm[m&1][i][mp[n]]*A[i]%mod)%mod;
    cout<<ret;
}
signed main(){
    A[0]=1;
    for(int i=1;i<40;i++)
    A[i]=A[i-1]*i%mod;
    int t=1;
    // t=read();
    while(t--)solve();
    return 0;
}
//「哎，我当然也不想跟你计较这些喔。」

// 护翼军第五师团，总团长室。
// 被甲族（Armado）一等武官抽着烟，吞云吐雾地说道：

//「不过你好歹身为武官，从铁丝网的洞钻出去买甜甜圈吃，感觉实在有病耶。」
// 有一项坏事露馅了。

//「既然要溜出去买东西，弄个军法严禁的酒才对嘛。那样的话，就算事情露馅了也比较光彩吧。」
// 不不不不不，这位大官，你在说什么啊？