CF1097D Makoto and a Blackboard

Description:

给定 \(n,k\)，一共会进行 \(k\) 次操作，每次操作会把 \(n\) 等概率的变成 \(n\) 的某个约数

求操作 \(k\) 次后 \(n\) 的期望是多少，答案对 \(10^9+7\) 取模

Hint:

\(n \le 10^{15} ,k \le 10^4\)

Solution:

学到新姿势了

考虑裸暴力dp

\(dp[i][k]=\sum_{j|i}dp[j][k-1]*\frac{1}{cnt}\)

显然T飞

我们发现答案满足积性

考虑把dp[i]拆成\(dp[p_0^{a_0}]*dp[p_1^{a_1}]*dp[p_2^{a_2}]\) 其中\(p_i\)为质数

这样状态数会大大减少,复杂度\(O(k*log^2n)\)

暴力记搜就行

#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const ll  mxn=1e4+5,mod=1e9+7;
ll  k,t,ans=1,dp[63][mxn];
ll n;

inline ll  read() {
    char c=getchar(); ll  x=0,f=1;
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
    return x*f;
}
inline ll  chkmax(ll  &x,ll  y) {if(x<y) x=y;}
inline ll  chkmin(ll  &x,ll  y) {if(x>y) x=y;}

ll  qpow(ll  a,ll  b) 
{
    ll  res=1,bs=a;
    while(b) {
        if(b&1) res=1ll*res*bs%mod;
        bs=1ll*bs*bs%mod;
        b>>=1;
    }
    return res;
}

ll  inv(ll  x) {return qpow(x,mod-2);}

ll  solve(ll  a,ll  cnt,ll  opt) 
{
    if(cnt==0) {
        dp[cnt][opt]=1;
        return 1;
    }
    if(opt==0) {
        if(!dp[cnt][opt]) dp[cnt][opt]=1ll*solve(a,cnt-1,opt)*a%mod;
        return dp[cnt][opt];
    }
    ll  res=0;
    for(ll  d=0;d<=cnt;++d) {
        if(!dp[d][opt-1]) dp[d][opt-1]=solve(a,d,opt-1);
        res=(res+dp[d][opt-1])%mod;
    }
    return (ll  ) (1ll*res*inv(cnt+1)%mod);
}

int  main()
{
    scanf("%lld",&n); k=read();
    for(ll  i=2;i*i<=n;++i) {
        if(n%i!=0) continue ; t=0;
        while(n%i==0) ++t,n/=i;
        memset(dp,0,sizeof(dp));
        ans=1ll*ans*solve(i,t,k)%mod;
    }
    memset(dp,0,sizeof(dp));
    if(n>1) ans=1ll*ans*solve(n,1,k)%mod;
    printf("%lld",ans);
    return 0;
}