HDU7047 Link With Balls

组合数学，思维

题目描述

There were a lot of balls in the factory of Ball Illusion Technology(BIT). Link, a boy, went there to get some balls, but suddenly, he found that there were too many ways to get balls.

There are $2n$ buckets in the factory. Link may get $kx$ balls from the $2x-1^{th}$ bucket, where $k $ is a non-negtive integer. He may also get at most $x$ balls from the $2x^{th}$ bucket.

Link wanted to get $m$ balls, and he wondered how many ways there were to take out exactly $m$ balls. While Link is calculating the answer, he wants you to calculate it as well, and you should output the answer modulo $10^9+7$.

输入

The input consists of multiple test cases.

The first line contains an integer $T (1≤T≤10^5)$ -- the number of test cases.

Each test case contains two integers $n$ and $m$$(1≤n,m≤10^6)$.

输出

For each test case, print the answer modulo $10^9+7$ in a single line.

中文题意

有$2n$个篮子，对于偶数篮子$2x$，可以任意从中取不超过$x$个球。对于奇数篮子$2x-1$，只能取$kx$个球，其中$k \geq 0$。问从中取出$m$个球的方案数。

题解

比赛的时候将奇数偶数分开考虑了，导致不能在规定时间内求出答案。

将可以取$0\sim k-1$个球的篮子，与能取$k$的倍数个球的篮子合并，合并之后的篮子能取任意多的球，并且方案唯一。

这时得到了$n$个可以取任意个球的篮子，还有一个可以取$0\sim n$个球的篮子。

于是枚举$0\sim n$的篮子中取了多少球，剩下取的球可以用插板法。

答案就是$\sum_{i=0}^{n}C_{m-i+n-1}^{n-1}$，即为$C_{m+n}^{n}-C_{m-1}^{n}$。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int ksm(int x, int y) {
    int res = 1;
    while(y) {
        if (y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}

int fac[2000006], inv[2000005];

int C(int n, int m) {
    if (n < m) return 0;
    return fac[n] * inv[m] % mod * inv[n-m] % mod;
}

signed main() {
    fac[0] = 1;
    for (int i = 1; i <= 2000000; i ++) fac[i] = fac[i - 1] * i  % mod;
    inv[2000000] = ksm(fac[2000000], mod - 2);
    for (int i = 1999999; i >= 0; i --)
        inv[i] = inv[i + 1] * (i + 1) % mod;
    int T;
    cin >> T;
    int n, m;
    while(T--) {
        scanf("%lld%lld", &n, &m);
        printf("%lld\n", ((C(m+n, n) - C(m-1, n)) % mod + mod) % mod);
    }
    return 0;
}