D 数列统计

题目地址：

https://ac.nowcoder.com/acm/contest/5881/D

基本思路：

(以下是不正经解法QAQ，正经解法可以看其他巨巨)
这题本来想正经的推一下式子的，结果组合数学太差了没想出来，所以就打表找规律了。
我们先附上打表用：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int mod = 911451407;
int l,x,ans = 0;
void dfs(int nxt,int step){
  if(step == l - 1){
    ans++;
    return;
  }
  for(int i = nxt ; i <= x ; i++){
    dfs(i,step + 1);
  }
}
signed main() {
  IO;
  int T;
  cin >> T;
  while (T--){
    cin >> l >> x;
    cout << "l: " << l << " x: " << x << " ";
    if(l == 1){
      puts("1");
      continue;
    }
    ans = 0;
    dfs(1,0);
    cout <<  ans <<'\n';
  }
  return 0;
}

然后我们固定一个量不变，比如我们设定l为3，那么能得到以下结果：

l: 3 x: 1 1
l: 3 x: 2 3
l: 3 x: 3 6
l: 3 x: 4 10
l: 3 x: 5 15
l: 3 x: 6 21
l: 3 x: 7 28
l: 3 x: 8 36
l: 3 x: 9 45

然后如果我们对组合数比较了解，那么其实我们能看出来这是的结果，而应该是等于，然后再带几个数字我们大概就能发现最终答案应该是，最后我们稍微对拍一下就能发现这个是对的。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define ll long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(ll x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

ll mod = 911451407;
const int maxn = 2000050;
ll qpow(ll a,ll x) {
  ll ret = 1;
  while (x) {
    if (x & 1)
      ret = ret * a % mod;
    a = a * a % mod;
    x >>= 1;
  }
  return ret;
}
ll fac[maxn],inv[maxn];
ll init() {
  fac[0] = 1;
  for (int i = 1; i < maxn; i++)
    fac[i] = fac[i - 1] * i % mod;
  inv[maxn - 1] = qpow(fac[maxn - 1], mod - 2);
  for (int i = maxn - 2; i >= 0; i--)
    inv[i] = inv[i + 1] * (i + 1) % mod;
  return 0;
}
ll c(ll n,ll m) {
  if (n < m) return 0;
  return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
signed main() {
  IO;
  init();
  int T;
  T = read();
  while (T--){
    int l = read(),x = read();
    if(l == 1 || x == 1){
      puts("1");
      continue;
    }
    l--; x--;
    ll ans = c(l + x,l);
    print(ans % mod);
    puts("");
  }
  return 0;
}