洛谷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\) 的值，分为两种情况讨论：

1. \(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}\) 。
2. \(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;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/chen196422803/solution-p9035

---

题外话：

㊗️新年快乐喵~💛