牛客周赛 Round 60 折返跑（组合数学）

题目链接：题目

大意：

在$1$到$n$之间往返跑m趟，推$m-1$次杆子，每次都向中间推，不能推零次，问有多少种推法（mod 1e9+7）。

思路：

一个高中学过的组合数学问题，实际上就是把$n-2$（不算两头）个位置分配给$m-1$次操作，也就是$C(n-2,m-1)$。
之后的关键在于怎么实现计算。计算组合数要涉及阶乘，阶乘每次计算费时间，那么我们可以用数组把阶乘计算结果储存起来 ，可以利用动态规划辅助计算。由于组合数设计除法，不方便取模，所以要计算逆阶乘，使用费马小定理，另外还需要快速幂计算乘方。

代码：

#include <bits/stdc++.h>  
using namespace std;  typedef long long ll;  const int MOD = 1e9 + 7;  
const int MAX = 1e6 + 5;  ll pow_mod_func(ll a, ll b, ll mod) {  ll res = 1;  a %= mod;  while(b > 0){  if(b & 1){  res = res * a % mod;  }  a = a * a % mod;  b >>= 1;  }  return res;  
}  ll fact[MAX];  
ll inv_fact_arr[MAX];  void precompute() {  fact[0] = 1;  for(int i = 1; i < MAX; ++i){  fact[i] = fact[i-1] * i % MOD;  }    inv_fact_arr[MAX-1] = pow_mod_func(fact[MAX-1], MOD-2, MOD);  for(int i = MAX-2; i >=0; --i){  inv_fact_arr[i] = inv_fact_arr[i+1] * (i+1) % MOD;  }  
}  ll comb(int n, int k){  if(k <0 || k >n) return 0;  return fact[n] * inv_fact_arr[k] % MOD * inv_fact_arr[n - k] % MOD;  
}  int main(){  ios::sync_with_stdio(false);  cin.tie(0);  precompute();  int t;  cin >> t;  while(t--){  int n, m;  cin >> n >> m;  int k = m -1;  if(k == 0){  cout << "1\n";  continue;  }  if(k > n - 2){  cout << "0\n";  continue;  }  ll ans = comb(n - 2, k);  cout << ans << '\n';  }  return 0;  
}