哈尔滨理工大学软件与微电子学院程序设计竞赛——K.Walk【逆元 组合数】

题目传送门

题解

• 按理说应该用dp进行转移

• 最短走法应该只往下和右

• $dp[i][j]=dp[i?1][j]+dp[i][j?1]$

• 但是这个$n，m$较大，不支持用二维数组和复杂度，并且还是多组输入

• 那么直接用组合数进行计算

• 从$(1,1)$到$(n,m)$的路径往右和往下总共走$n+m?2$次

• 其中往下走包括$n?1$次，那么直接$C_{n+m?2}^{n?1}$

• 从$n+m?2$步中选出$n?1$步往下走，剩下的步数往右走

• 所以直接预处理+逆元使用组合数

AC-Code

#include <bits/stdc++.h>
using namespace std;const int maxn = (1e6+7)*2;
const int mod = 1e9 + 7;typedef long long ll;ll factorial[maxn] = {
     1 }; // 阶乘ll q_pow(ll a, ll b, ll mod) {
     // 快速幂ll res = 1LL;while (b) {
    if (b & 1)  res = (res * a) % mod;a = (a * a) % mod;b >>= 1;}return res % mod;
}ll inv(ll x) {
    return q_pow(x, mod - 2, mod);
}ll C(ll n, ll k) {
    return factorial[n] * inv(factorial[n - k] * factorial[k] % mod) % mod;
}int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);factorial[0] = 1;for (int i = 1; i <= maxn - 5; ++i)factorial[i] = (factorial[i - 1]) * i % mod;;int T;  cin >> T;while (T--) {
    ll N, M;    cin >> N >> M;cout << C(N + M - 2, N - 1) % mod << endl;}
}