AT_abc034_c 题解

· · 题解

AT_abc034_c 题解

思路

下文将题目输入的 W,H 分别称为 N,M，并认为 N,M 同阶。

如果直接 DP，时间复杂度 \mathcal{O}(N^2)，稳稳 TLE。

不难发现，对于一个 N 行 M 列的网格，从左上角走到右下角，一共需要走 N-1 次向下，M-1 次向右。

所以问题可以转化成，给定 N-1 个 0 和 M-1 个 1，询问可以拼出多少个不同的 01 串，答案对 10^9+7 取模。

发现总长度是 N+M-2，所以问题又转化成，给定 N+M-2 个空位，要求在这些空位中放入 N-1 个物品，每个空位最多放一个，求方案数量。

为了方便，这里把 N,M 都自减 1。

很显然这是一个排列组合 C_{N+M}^N。

根据 C_{m}^{n} = \frac{m!}{(m-n)!n!} 推一下式子：

\begin{aligned} C_{N+M}^N & = \frac{(N+M)!}{(N+M-N)!N!} \\ & = \frac{(N+M)!}{M!N!} \end{aligned}

所以只需要求出 N+M 的阶乘，求出 M!N! 的逆元，两者相乘即为结果。

时间复杂度：\mathcal{O}(N)。

代码

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define endl '\n'
#define FRR(file) freopen(file,"r",stdin)
#define FRW(file) freopen(file,"w",stdout)
#define _rep(i,a,b) for (int i=(a);i<=(b);++i)
#define _reps(i,a,b,c) for (int i=(a);i<=(b);c)
#define _rrep(i,a,b) for (int i=(a);i>=(b);--i)
#define _rreps(i,a,b,c) for (int i=(a);i>=(b);c)
#define _iter(i,a) for (auto i=a.begin();i!=a.end();++i)

const int mod=1e9+7;

int n,m;

int exgcd(int a,int b,int& x,int& y) {
    if (!b) {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

int fact(int k) {
    int ans=1;
    _rep(i,2,k) ans=ans*i%mod;
    return ans;
}

int inv(int k) {
    int x,y;
    exgcd(k,mod,x,y);
    return (x%mod+mod)%mod;
}

signed main() {
    scanf("%lld %lld",&n,&m); n--,m--;
    printf("%lld\n",fact(n+m)*inv(fact(n)*fact(m)%mod)%mod);
    return 0;
}