CC

自然万物都趋向从有序变得无序

0%

HDU 6363 bookshelf (容斥)

发表于 更新于 分类于 Valine：

题目链接

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Patrick Star bought a bookshelf, he named it ZYG !! Patrick Star has N book . The ZYG has K layers (count from 1 to K) and there is no limit on the capacity of each layer ! Now Patrick want to put all N books on ZYG : 1. Assume that the i-th layer has cnti(0≤cnti≤N) books finally.

  1. Assume that f[i] is the i-th fibonacci number (f[0]=0,f[1]=1,f[2]=1,f[i]=f[i−2]+f[i−1]).

  2. Define the stable value of i-th layers stablei=f[cnti].

  3. Define the beauty value of i-th layers beautyi=2stablei−1.

  4. Define the whole beauty value of ZYG score=gcd(beauty1,beauty2,…,beautyk)(Note: gcd(0,x)=x).

    Patrick Star wants to know the expected value of score if Patrick choose a distribute method randomly !

Input

The first line contain a integer T (no morn than 10), the following is T test case, for each test case :
Each line contains contains three integer n,k(0<n,k≤1e6).

Output

For each test case, output the answer as a value of a rational number modulo 1e9+7. Formally, it is guaranteed that under given constraints the probability is always a rational number p/q (p and q are integer and coprime, q is positive), such that q is not divisible by 1e9+7. Output such integer a between 0 and 1e9+6 that p−aq is divisible by 1e9+7.

Sample intput

1
6 8

Sample Output

797202805

题意:

有k层书架，n本书，现将n本书放到k层书架上，假设当前层书架上有num本书，那么此层会得到一个分数，定义为：2^fib(num) - 1；整个书架的分数为每层的gcd，求期望的分数。

思路:

考虑算出所有情况的分数和，然后除以有多种情况。

首先介绍两个性质：设fib为斐波那契数列；gcd(fib(n), fib(m)) = fib(gcd(n,m))

gcd(k^n - 1, k^m - 1) = k^(gcd(m, n)) - 1;

那么我们考虑化简题目给定的公式：score=gcd(2fib(cnti)−1,2fib(cntj)−1,...)=2gcd(fib(cnti),fin(cntj),...)−1=2fibgcd(i,j,...)−1score = gcd(2^{fib(cnt_i)} - 1, 2 ^{fib(cnt_j)} - 1,...) = 2^{gcd(fib(cnt_i), fin(cnt_j), ...)} - 1 = 2 ^ {fib_{gcd(i, j,...)}}-1

那么我们考虑枚举gcd，算出当d = gcd的时候有多少种情况，然后除以总的情况数就得到了期望。

当d = gcd时，我们知道每层的数目一定是gcd的倍数，那么n个数可以有n/d个系数用来分配到每层，这样能保证它们的gcd = d。那么对于分配的方法，根据插板法，共有C(n/d+k-1, k-1) 种。

然后就需要容斥了，因为我们之前那么分配还会产生gcd为d的倍数，我们需要减去gcd的倍数的情况。

那么我们只需要逆序 处理就行了。

代码:

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 /***********************************************************************
  > Author: wood
  > Mail: cbcruel@gmail.com
  > Created Time: 2018年03月20日 星期二 17时51分10秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<ctime>
#include<string>

using namespace std;
typedef long long  LL;
typedef long long ll;
const double eps = 1e-8;
const double C = 0.57721566490153286060651209;
const double pi = acos(-1.0);
const int maxn = 2e6+10;
const LL mod = 1e9 + 7;
const LL INF = 1e18;
#define sqr(x) (x)*(x)

LL ni[maxn], fi[maxn],f[maxn/2], inv[maxn];
int vis[maxn/2];
vector<int> v;
LL d[maxn/2];

LL qpow(LL x, LL n){
    LL ans = 1;
    x %= mod;
    while(n){
        if(n&1) ans = ans * x % mod;
        x = x * x % mod;
        n >>= 1;
    }return ans;
}

void init(){
    ni[0] = fi[0] = 1;
    inv[0]=inv[1]=1;//1 ~ n每个数的逆元
    for(int i = 2;i < maxn; ++i) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
    for(int i = 1; i < maxn; ++i){
        fi[i] = fi[i-1] * i % mod;
        ni[i] = ni[i-1] * inv[i] % mod;
    }f[1] =1;f[0] = 0;
    for(int i = 2; i < maxn/2; ++i){
        f[i] = (f[i-1] + f[i-2]);
        vis[i] |= vis[i-1];
        if(f[i] >= mod-1)
            vis[i] = 1;
        f[i] %= (mod-1);
    }
}

LL cal(int n, int m){
    if(n < m) return 0LL;
    return fi[n] * ni[m] % mod * ni[n-m] % mod;
}

int main(){
    int t;
    init();
    scanf("%d", &t);
    while(t--){
        int n,k;
        v.clear();
        scanf("%d %d", &n, &k);
        for(int i = 1; i <= n; ++i) if(n%i == 0) v.push_back(i);
        for(int i = 0; i < v.size(); ++i) d[i] = cal(n/v[i]+k-1,k-1);
        LL ans = 0;
        for(int i = v.size()-1; i >= 0; --i){
            for(int j = i + 1; j < v.size(); ++j)
                if(v[j] % v[i] == 0)
                    d[i] =(d[i] -  d[j] + mod) % mod;
        }
        for(int i = 0; i < v.size(); ++i)
            (ans += d[i] * (qpow(2LL, f[v[i]]+ vis[v[i]]*(mod-1))-1)% mod) %= mod;
        (ans += mod) %= mod;
        printf("%lld\n",ans * qpow(cal(n+k-1,k-1),mod-2) % mod);
    }   return 0;
}