洛谷P9035 「KDOI-04」Pont des souvenirs 题解

算法数学

发布日期: 2024-01-01

更新日期: 2024-01-01

文章字数: 726

洛谷P9035 「KDOI-04」Pont des souvenirs 题解

题目链接：P9035 「KDOI-04」Pont des souvenirs

题意：

给定正整数 $n,k$，求有多少个长度为 $n$ 的正整数序列 $a$ 满足：

$0<a_1\le a_2\le a_3\le\cdots\le a_n\le k$；

$\forall\ i\not=j$，$a_i+a_j\le k+1$。

答案对 $10^9+7$ 取模。

输入格式：

本题包含多组测试数据。

输入的第一行包含一个正整数 $T$，表示测试数据组数。

对于每组测试数据，输入包含一行两个正整数 $n,k$。

输出格式：

对于每组测试数据，输出一行一个整数表示答案。

数据范围：

对于 $100\%$ 的数据，保证 $1\le T\le2\times10^5$，$1\le n,k\le10^7$

设 $a_0 = 1$ ，并记 $b_i = a_i - a_{i - 1}$ 。考虑枚举 $a_n$ 的值，分为两种情况讨论：

$a_n \le \left\lfloor\frac{k+1}{2}\right\rfloor$ ，此时不用考虑第二条限制，只需满足 $\left(\sum_{i=1}^n b_i\right)=a_n-1$ ，即可重组合数 $H_{n}^{a_n - 1}$ 。
$a_n > \left\lfloor\frac{k+1}{2}\right\rfloor$ ，此时要考虑第二条限制，即 $a_{n - 1} \le k + 1 - a_n$ 。容易发现此时等价于 $H_{n}^{k+1-a_n}$

那么答案其实就是

$\sum_{i=1}^{\left\lceil\frac{k}{2}\right\rceil}\left(\begin{array}{c} n+i-2 \\ i-1 \end{array}\right)+\sum_{i=1}^{\left\lfloor\frac{k}{2}\right\rfloor}\left(\begin{array}{c} n+i-2 \\ i-1 \end{array}\right)$

或者？

$\sum_{i=1}^{\left\lceil\frac{k}{2}\right\rceil}\left(\begin{array}{c} n+i-2 \\ n-1 \end{array}\right)+\sum_{i=1}^{\left\lfloor\frac{k}{2}\right\rfloor}\left(\begin{array}{c} n+i-2 \\ n-1 \end{array}\right)$

这里需要讲一个组合数求和结论

$\sum_{i=l}^r\binom{i}{k}=\binom{r+1}{k+1}-\binom{l}{k+1}$

证明的话，只需要移项计算即可。

那么原式又可以写成

$\binom{n+\left\lceil\frac{k}{2}\right\rceil-1}{n}+\binom{n+\left\lfloor\frac{k}{2}\right\rfloor-1}{n}$

时间复杂度 $\mathcal{O}(V)$ ，即 $n+k$ 的值域。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e7 + 15))

int fac[N], inv[N];
int qpow(int a, int b)
{
    int r = 1;
    while(b)
    {
        if(b & 1) r = r * a % mod;
        b >>= 1; a = a * a % mod;
    }
    return r;
}
void init(int n)
{
    fac[0] = 1;
    for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
    inv[n] = qpow(fac[n], mod - 2);
    for(int i = n - 1; ~i; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
}
int C(int n, int m)
{
    if(m < 0 || n < m) return 0;
    return fac[n] * inv[n - m] % mod * inv[m] % mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int T,n,k; init(2e7);
    cin >> T; while(T--)
    {
        cin >> n >> k;
        cout << (C(n + (k + 1) / 2 - 1, n) + C(n + k / 2 - 1, n)) % mod << '\n';
    }
    return 0;
}