「Codeforces 1097D」Makoto and a Blackboard

发表于 | | 阅读次数:
字数统计: 1k 字

Description

题目链接：Codeforces 1097D

Makoto 有一个大黑板，上面写着一个正整数 $n$，他将会进行恰好 $k$ 次操作：

假设黑板上的数字是 $v$，他会随机选择一个 $v$ 的约数（可能是 $1$ 或 $v$）然后用这个约数替换 $v$。保证每个约数被选择的概率相同。

他想知道 $k$ 次操作后黑板上的数字的期望值是多少。答案对 $10^9+7$ 取模。

数据范围：$1\le n\le 10^{15}$，$1\le k\le 10^4$

Solution

我们定义 $f(i,j)$ 表示操作 $i$ 次后得到数字 $j$ 的概率。发现每个质因子都是相互独立的，每次改变的只不过是若干个质因子的指数。那么这意味着 $f$ 是一个积性函数！

考虑对于 $n$ 的一个质因子 $p$，其指数为 $c$，那么设 $g(i,j)$ 表示数字 $p^c$ 操作 $i$ 次后指数为 $j$ 的概率。转移方程为：

这个式子的含义是：指数 $j$ 可以由指数 $j\sim c$ 转移过来，对于原来的指数 $k$，有 $\frac{1}{k+1}$ 的概率转移到现在的指数 $j$（其实这个式子可以前缀和优化，复杂度由 $O(kc^2)$ 优化为 $O(kc)$，但是由于 $c\le \log n$，因此无关紧要）。

那么数字 $p^c$ 操作后的期望为：

最终的答案为所有质因子答案的乘积（积性函数的定义）。

时间复杂度：$O(k\log^3 n)$（非常不满），优化后为 $O(k\log^2 n)$

Code

朴素写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
#include <cstdio>
#include <cstring>
#include <vector>

const int K=1e4+5,logN=51;
const int mod=1e9+7;
long long n;
int k,f[K][logN],inv[logN];
std::vector<std::pair<int,int> > v;

void getFactor(long long n) {
    for(int i=2;1LL*i*i<=n;++i) {
        if(n%i) continue;
        int cnt=0;
        while(n%i==0) n/=i,++cnt;
        v.push_back(std::make_pair(i,cnt));
    }
    if(n>1) v.push_back(std::make_pair(n%mod,1));
}
void initInv() {
    inv[0]=inv[1]=1;
    for(int i=2;i<logN;++i) inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
}
int pow(int x,int p) {
    int ans=1;
    for(;p;p>>=1,x=1LL*x*x%mod) if(p&1) ans=1LL*ans*x%mod;
    return ans;
}
void upd(int &x,int y) {
    (x+=y)>=mod&&(x-=mod);
}
int solve(int p,int c) {
    memset(f,0,sizeof(f));
    f[0][c]=1;
    for(int i=1;i<=k;++i) for(int j=0;j<=c;++j) {
        for(int l=j;l<=c;++l) upd(f[i][j],1LL*f[i-1][l]*inv[l+1]%mod);
    }
    int ans=0;
    for(int i=0;i<=c;++i) upd(ans,1LL*f[k][i]*pow(p,i)%mod);
    return ans;
}
int main() {
    scanf("%lld%d",&n,&k);
    getFactor(n);
    initInv();
    int ans=1;
    for(std::pair<int,int> x:v) ans=1LL*ans*solve(x.first,x.second)%mod;
    printf("%d\n",ans);
    return 0;
}

前缀和优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
#include <cstdio>
#include <cstring>
#include <vector>

const int logN=51;
const int mod=1e9+7;
long long n;
int k,f[logN],inv[logN],s[logN];
std::vector<std::pair<int,int> > v;

void getFactor(long long n) {
    for(int i=2;1LL*i*i<=n;++i) {
        if(n%i) continue;
        int cnt=0;
        while(n%i==0) n/=i,++cnt;
        v.push_back(std::make_pair(i,cnt));
    }
    if(n>1) v.push_back(std::make_pair(n%mod,1));
}
void initInv() {
    inv[0]=inv[1]=1;
    for(int i=2;i<logN;++i) inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
}
int pow(int x,int p) {
    int ans=1;
    for(;p;p>>=1,x=1LL*x*x%mod) if(p&1) ans=1LL*ans*x%mod;
    return ans;
}
void upd(int &x,int y) {
    (x+=y)>=mod&&(x-=mod);
}
int solve(int p,int c) {
    memset(f,0,sizeof(f)),memset(s,0,sizeof(s));
    f[c]=1,s[c]=f[c]*inv[c+1];
    for(int i=1;i<=k;++i) {
        for(int j=0;j<=c;++j) f[j]=(s[c]-(j?s[j-1]:0)+mod)%mod;
        for(int j=0;j<=c;++j) s[j]=1LL*f[j]*inv[j+1]%mod;
        for(int j=1;j<=c;++j) upd(s[j],s[j-1]);
    }
    int ans=0;
    for(int i=0;i<=c;++i) upd(ans,1LL*f[i]*pow(p,i)%mod);
    return ans;
}
int main() {
    scanf("%lld%d",&n,&k);
    getFactor(n);
    initInv();
    int ans=1;
    for(std::pair<int,int> x:v) ans=1LL*ans*solve(x.first,x.second)%mod;
    printf("%d\n",ans);
    return 0;
}
0%