题目概述

有 $n$ 个物品，分配到 $m$ 个箱子里（可以为空），问 $(2^{fib_{a_1} }-1,2^{fib_{a_2} }-1,\cdots,2^{fib_{a_m} })$ 的期望。

解题报告

出现了两种很特殊的数：斐波那契数和 $2^{x}-1$ 。搞事情开始：

$$ (2^{a}-1,2^{b}-1)=(2^{a}-1,2^{a}-2^{b})=(2^{a}-1,2^{b}(2^{a-b}-1))\\ ∵ (2^{b},2^{b}-1)=1∴ (2^{a}-1,2^{b}(2^{a-b}-1))=(2^{a}-1,2^{a-b}-1) $$

也就是说 $(2^{a}-1,2^{b}-1)=2^{(a,b)}-1$ 。然后再上个结论：$(fib_a,fib_b)=fib_{(a,b)}$ (反正我不会证)，就可做了：

$$ ans={\sum2^{fib_{(a_1,a_2,\cdots,a_m)}\ mod\ (MOD-1)}\over{n+m-1\choose m-1} } $$

看到 $gcd$ 果断用 $\mu$ 换掉：

$$ \sum_{d}2^{fib_{d} }\sum[(a_1,a_2,\cdots,a_m)=d]=\sum_{d}2^{fib_d}\sum_{k}\mu(k)\sum[\sum_{i=1}^{m}{a_i\over dk}={n\over dk}] $$

最后那个式子显然是隔板法，方案数为 ${n\over dk}+m-1\choose m-1$ ，但如果暴力枚举上面的式子由于多组数据可能会TLE，所以把式子变形一下：

$$ \sum_{T|n}{ {n\over T}+m-1\choose m-1}\sum_{d|T}2^{fib_d}\mu({T\over d}) $$

后面那部分可以调和级数预处理，然后复杂度就正常了。

示例程序

#include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL;
const int maxn=1000000,maxt=2000000,MOD=1e9+7;

int te,n,m,all,f[maxn+5],pw[maxn+5],fac[maxt+5],INV[maxt+5],ans;
int p[maxn+5],mu[maxn+5],pre[maxn+5];bool pri[maxn+5];

inline void fib(int &x,int tem) {if ((x+=tem)>=MOD-1) x-=MOD-1;}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline int Pow(int w,int b) {int s=1;for (;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void Make(){
    f[0]=0;pw[0]=1;f[1]=1;pw[1]=2;for (int i=2;i<=maxn;i++) fib(f[i]=f[i-1],f[i-2]),pw[i]=Pow(2,f[i]);
    INV[0]=INV[1]=fac[0]=1;for (int i=2;i<=maxt;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    for (int i=1;i<=maxt;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=(LL)INV[i]*INV[i-1]%MOD;
    pri[0]=pri[1]=true;mu[1]=1;
    for (int i=2;i<=maxn;AMOD(mu[i],MOD),i++){
        if (!pri[i]) p[++p[0]]=i,mu[i]=-1;
        for (int j=1,t;j<=p[0]&&(t=i*p[j])<=maxn;j++)
            if (i%p[j]) mu[t]=-mu[i],pri[t]=true; else {mu[t]=0;pri[t]=true;break;}
    }
    for (int i=1;i<=maxn;i++)
        for (int j=i;j<=maxn;j+=i)
            AMOD(pre[j],(LL)pw[i]*mu[j/i]%MOD);
}
#define C(x,y) ((LL)fac[x]*INV[y]%MOD*INV[(x)-(y)]%MOD)
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (Make(),scanf("%d",&te);te;te--){
        scanf("%d%d",&n,&m);all=C(n+m-1,m-1);ans=0;
        for (int i=1,S=sqrt(n);i<=S;i++)
            if (!(n%i)){
                AMOD(ans,C(n/i+m-1,m-1)*pre[i]%MOD);
                if (i!=n/i) AMOD(ans,C(i+m-1,m-1)*pre[n/i]%MOD);
            }
        AMOD(ans,MOD-all);ans=(LL)ans*Pow(all,MOD-2)%MOD;printf("%d\n",ans);
    }
    return 0;
}