牛客IOI周赛17-普及组数列统计（组合数）tomjobs的博客-牛客ioi周赛17-普及组

链接：https://ac.nowcoder.com/acm/contest/5881/D
来源：牛客网

题目描述
求以xx结尾的长度为ll的不下降正整数数列一共有多少个。对911451407911451407取模
输入描述:
textbf{本题有多组数据。}本题有多组数据。
第一行一个正整数TT，表示数据组数。

对于每组数据：两个用空格隔开的整数l, xl,x。

输出描述:
TT行，每行一个答案。
示例1
输入
复制
2
2 1
2 3
输出
复制
1
3
备注:
对于前10%10%的数据,T = 10; l, x leq 10T=10;l,x≤10
对于前20%20%的数据,T = 10;l, x leq 1000T=10;l,x≤1000
对于前40%40%的数据,T = 10;l, x leq 10^5T=10;l,x≤10
5

对于100%100%的数据,T leq 10^5; 0 < l, x leq 10^6T≤10
5
;0<l,x≤10
6

思路：
定义
$f[x][l]$

f[x][l]代表结尾数为
$x$

x且长度为
$l$

l的方案数。
那么
$f[x][l]$

f[x][l]=
$∑f[k][l-1]$

∑f[k][l−1]
$(1≤k≤x)$

(1≤k≤x)

那么
$f[x][l]$

f[x][l]=
$f[x-1][l]+f[x][l-1]$

f[x−1][l]+f[x][l−1]
这实际就相当于
$x*l$

x∗l的平面，从(1,1)出发走到(x,l)，只从往右和往下走。
所以答案是
$C(x+l-2,x-1)$

C(x+l−2,x−1)

#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <vector> #include <queue> #include <iostream> #include <map> #include <string> using namespace std; typedef long long ll; const int mod = 911451407; const int maxn = 2e6 + 7;  ll fac[maxn],inv[maxn];  ll qpow(ll a,ll b) {     ll res = 1; while(b) { if(b & 1) {             res = (res * a) % mod; }         a = (a * a) % mod;         b = b >> 1; } return res % mod; }  ll C(ll n,ll m) { if(m > n || m < 0) return 0; return fac[n] * ((inv[n - m] * inv[m]) % mod) % mod; } void init() {     fac[0] = 1;     inv[0] = 1; for(int i = 1;i <= maxn - 2;i++) {         fac[i] = (fac[i - 1] * i) % mod;         inv[i] = qpow(fac[i],mod - 2); } } int main() { init(); int T;scanf("%d",&T); while(T--) { int l,x;scanf("%d%d",&l,&x); swap(l,x); printf("%lldn",C(x + l - 2,l - 1)); } return 0; }