D 数列统计_牛客博客

本意是 $O(1)$ 组合数，没想到数据太水，让 $O(log \ 911451405)$ 组合数过了，在此谢罪了。

设 $L_{x,y}$ 表示最大数为 $y$ , 长度为 $x$ 的不下降正整数数列的个数。

$L_{x,y} = \begin{cases} 1 & \text{x = 0}\\ \sum_{i = 1}^{y}{L_{x - 1,i}} \ \Rightarrow \ L_{x,y - 1} + L_{x - 1,y} & \text{x > 0} \end{cases}$

x\y	1	2	3	4	5	6	7	8	9	10	11	12
0	1	1	1	1	1	1	1	1	1	1	1	1
1	1	2	3	4	5	6	7	8	9	10	11
2	1	3	6	10	15	21	28	36	45	55
3	1	4	10	20	35	56	84	120	165
4	1	5	15	35	70	126	210	330
5	1	6	21	56	126	252	462
6	1	7	28	84	210	462
7	1	8	36	120	330
8	1	9	45	165
9	1	10	55
10	1	22
11	1

由

$L_{x,y} = \begin{cases} 1 & \text{x = 0}\\ L_{x,y - 1} + L_{x - 1,y} & \text{x > 0} \end{cases}$

看出 $L_{x,y}$ 是杨辉三角的第 $x + y$ 行，第 $y$ 列

而杨辉三角第 $n$ 行，第 $m$ 列代表 $C_{n - 1}^{m - 1}$

易得出 $L_{x,y} = C_{x + y - 1}^{y - 1}$

而原问题可转为最大数为 $x$ , 长度为 $l - 1$ 的不下降正整数数列。

故原问题的公式为 $C_{l + x - 2}^{x - 1}$ 。

$code :$

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
typedef long long LL;
const int maxn = 2e6, mod = 911451407;

int re[maxn + 10], inv[maxn + 10], fac[maxn + 10];

inline void init(int n) {
    re[0] = inv[1] = fac[0] = re[1] = fac[1] = 1;
    for (int i = 2; i <= n; ++i) {
        fac[i] = (LL)fac[i - 1] * i % mod;
        inv[i] = (LL)(mod - mod / i) * inv[mod % i] % mod;
        re[i] = (LL)re[i - 1] * inv[i] % mod;
    }
}

inline int C(int a,int b) {
    if (a < b) return 0;
    return (LL)fac[a] * re[b] % mod * re[a - b] % mod;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    init(2e6);
    int T;
    cin >> T;
    int l, x;
    do {
        cin >> l >> x;
        --l;
        cout << C(l + x - 1, x - 1) << '\n';
    } while (--T);
    return 0;
}