【规律】【容斥】HDU6363 bookshelf

分析：

援引dls的一句话：像这么恶心的题面，如果没有一个神奇的规律，就根本没法做嘛。。。
考场上我勉强证明了一下。。但考完之后发现那个证明似乎是错的。。。这里就不写了

我们可以尝试打个表：

（打表一定要精确啊！！我考场上就是计算器按错键，结果对着错的表磨了半天。。直到我队友打了一个表才发现。。。）

稍微写个程序质因数分解一下，发现255=3*5*17，8191是个质数，17179869183（我记不得了。。。反正是3的倍数）

诶。。9和6刚好也是3的倍数。。。

所以规律就有了：
一个数是另一个数的倍数的条件是：它的序号也是另一个的倍数。

好吧，那么gcd的规律呢？。。。考虑到斐波那契数列会很大，如果某个方案的gcd不是2的整次幂-1，那么斐波那契数列作为次数，就不能取模。。。就炸掉了。。。

所以反向推理一下，猜出另一个性质：两个数的gcd，等于它们的序号gcd的那个位置的值。（即6号与9号的值的gcd为3号的值）。这样的话，最终答案一定是2的整次幂-1，所以可以把斐波那契数列$mod (\varphi(10^9+7))$

有这么一堆性质，那最终答案就非常简单了。
就可以枚举最小的一层有多少个，令其他层数的数量为其倍数即可。
设枚举的值为m，如果$n\space mod\space m≠0$，不合法，直接跳过。
否则记$n1=\frac n m$
然后就可以直接用组合数求出这个方案：把n1本书放入k个柜子的任意摆放方案为$C_{n1+k-1}^{k-1}$

但这样会算重（因为这个方案数包含了最小一层是m的倍数而不是m的情况），在所有m的倍数的贡献中减去m算过的贡献即可。（调和级数logn的复杂度）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 2000010
#define MOD 1000000007
using namespace std;
typedef long long ll;
int n,m,k;
ll fi[MAXN],fac[MAXN],ifac[MAXN],dp[MAXN],val[MAXN];
ll fsp(ll x,ll y){ll res=1;while(y){if(y&1ll)res=res*x%MOD;x=x*x%MOD;y>>=1ll;    }return res;
}
ll C(int n,int m){return fac[n]*ifac[m]%MOD*ifac[n-m]%MOD;    
}
ll solve(int x){if(n%x!=0)return 0;int s=n/x;return C(k+s-1,k-1)%MOD;
}
int main(){int t;SF("%d",&t);while(t--){SF("%d%d",&n,&k);    fi[0]=0;fi[1]=1;for(int i=2;i<=n;i++)fi[i]=(fi[i-1]+fi[i-2])%(MOD-1);fac[0]=1;for(int i=1;i<=n+k;i++)fac[i]=fac[i-1]*i%MOD;ifac[k+n]=fsp(fac[k+n],MOD-2);for(int i=n+k;i>0;i--)ifac[i-1]=ifac[i]*i%MOD;ll sum=C(n-1+k,k-1);ll ans=sum;for(int i=1;i<=n;i++)if(n%i==0)val[i]=(fsp(2,fi[i])-2ll)%MOD;for(int i=1;i<=n;i++){if(n%i!=0)continue;ll sumx=solve(i);(ans+=sumx*val[i])%=MOD;for(int j=i+i;j<=n;j+=i)val[j]-=val[i];}    //PF("[%lld %lld]",ans,sum);(ans*=fsp(sum,MOD-2))%=MOD;PF("%lld\n",(ans+MOD)%MOD);}
}