【2018 HDU 多校 Contest 6 / 6363】Bookshelf / 题解

题目描述

你有 $N$ 本书和一个 $K$ 层的书架。

随机地将 $N$ 本书放进书架,这个时候第 $i$ 层的书本数量为 $cnt_i$。

令 $f_i$ 为第 $i$ 个 $Fibonacci$ 数($f_0=0, f_1=1, f_2=1, f_i=f_{i-1}+f_{i-2}$)。

令第 $i$ 层的美丽值 $beauty_i=2^{f_{cnt_i}}-1$,

则这个书架的总得分 $score=gcd(beauty_1, beauty_2, beauty_3, …, beauty_K)$。

现在给定 $N$ 和 $K$,求书架的得分的期望值。

输入和输出

输入

第一行是一个不超过 10 的正整数 $T$,代表有 $T$ 组测试数据。

接下来 $T$ 行,每行包含两个整数 $N, K$ ($0 < N, K leq 10^6$)。

输出

一共 $T$ 行。对于每一组数据,输出答案在模 $10^9+7$ 意义下的值。

样例

输入

1
6 8

输出

797202805

思路

我们知道, $gcd(x^a-1,x^b-1)=x^{gcd(a,b)}-1$ 。

所以我们就可以将 $gcd(beauty_1, beauty_2, beauty_3, …, beauty_k)$ 转化为 $2^{gcd(f_{cnt_1},f_{cnt_2},…,f_{cnt_k},)}-1$。

我们也可以轻易地证明 $gcd(f_x,f_y)=f_{gcd(x,y)}$。

所以我们最终得到了这个公式

$2^{f_{gcd(cnt_1,cnt_2,…,cnt_k}}-1$。

枚举每个可能的 $gcd$, 计算它的贡献。莫比乌斯反演即可。

首先,将 $N$ 分成 $K$ 个 $gcd$ 的倍数有 $C_{frac n{gcd}+k-1}^{k-1}$ 种方案,所以每个 $gcd$ 对答案的贡献为 $C_{frac n{gcd}+k-1}^{k-1} imes (2^{f_{gcd}}-1)$。

为了避免重复计算,使用莫比乌斯系数容斥。

没了。

代码

#include 
#define maxn 2000010
#define mod 1000000007
#define ll long long
using namespace std;
int pri[maxn],top;
bool vis[maxn];
int mu[maxn],fib[maxn],k;
ll ny[maxn],jc[maxn];
ll ksm(ll a,ll b){
    ll res=1;
    while(b){
        if (b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void Init(int n){
    ny[0]=jc[0]=fib[1]=mu[1]=1;
    for (int i=2;i<=n;i++){
        if (!vis[i]) pri[++top]=i,mu[i]=-1;
        for (int j=1;j<=top&&i*pri[j]<=n;j++){
            vis[i*pri[j]]=1;
            if (i%pri[j]==0) break;
            mu[i*pri[j]]=-mu[i];
        }
    }
    for (int i=1;i<=n;i++)
        jc[i]=jc[i-1]*i%mod;
    ny[n]=ksm(jc[n],mod-2);
    for (int i=n-1;i>=0;i--)
        ny[i]=(ny[i+1]*(i+1))%mod;
    for (int i=2;i<=n;i++)
    fib[i]=(fib[i-1]+fib[i-2])%(mod-1);
}
ll C(int n,int m){
    if (n==m||m==0) return 1;
    return jc[n]*ny[m]%mod*ny[n-m]%mod;
}
ll cc(int n){
    ll res=0;
    for (int i=1;i<=n;i++)
        if (n%i==0) res=(res+mu[i]*C(n/i+k-1,k-1)%mod+mod)%mod;
    return res;
}
ll kk(int n){
    return (ksm(2,fib[n])-1+mod)%mod;
}
int main(){
    ios::sync_with_stdio(false);
    Init(maxn-1);
    int T;cin>>T;while(T--){
        int n;
        ll ans=0;
        cin>>n>>k;
        for (int i=1;i*i<=n;++i){
            if (n%i==0){
                ans=(ans+cc(n/i)*kk(i)%mod)%mod;
                if (i*i!=n) ans=(ans+cc(i)*kk(n/i)%mod)%mod;
            }
        }
        cout<
Show Comments