CF1097D Makoto and a Blackboard

题目
一个较为直观的想法是把所有因数找出来，暴力dp跑\(k\)轮，复杂度bomb。
然后我们仔细观察一下，这个答案显然是一个积性函数，我们可以把\(n\)拆成若干个\(p^a\)分别跑然后乘起来。
这样的话复杂度就没问题了，可以用矩阵快速幂优化转移过程，但是没有必要。

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int N=51,P=1000000007;
ll n,pr[N];int m,K,inv[51],f[51],g[51],cnt[N],sz;
void inc(int &a,int b){a+=b,a=a>=P? a-P:a;}
int mul(int a,int b){return 1ll*a*b%P;}
int power(int a,int k){int r=1;for(;k;k>>=1,a=mul(a,a))if(k&1)r=mul(a,r);return r;}
void initfac(ll x=n)
{
    for(int i=2;1ll*i*i<=x;++i) if(!(x%i)) for(pr[++m]=i;!(x%i);x/=i,++cnt[m]);
    if(x^1) pr[++m]=x%P,cnt[m]=1;
}
int main()
{
    cin>>n>>K,initfac();int i,j,k,o,ans=1,sum;
    for(inv[1]=1,i=2;i<=50;++i) inv[i]=mul(P-P/i,inv[P%i]);
    for(i=1;i<=m;++i)
    {
    memset(f,0,sizeof f),f[cnt[i]]=1,sum=0;
        for(j=1;j<=K;++j)
    {
        memcpy(g,f,sizeof g),memset(f,0,sizeof f);
        for(k=0;k<=cnt[i];++k) for(o=k;o<=cnt[i];++o) inc(f[k],mul(g[o],inv[o+1]));
        }
    for(j=0;j<=cnt[i];++j) inc(sum,mul(f[j],power(pr[i],j)));
    ans=mul(ans,sum);
    }
    cout<<ans;
}

CF1097D Makoto and a Blackboard

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/11727168.html