1 条题解

  • 0
    @ 2023-10-1 16:46:12

    来了

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long ll;
    const int mod = 1e9 + 7;
    
    const int maxn = 2e5 + 7;
    ll f[maxn],fac[maxn],inv[maxn];
    
    struct P
    {
        ll x,y;
    }p[maxn];
    
    ll qpow(ll x,ll n)
    {
        ll res = 1;
        while(n)
        {
            if(n & 1)
                res = (res * x) % mod;
            x = (x * x) % mod;
            n >>= 1;
        }
        return res;
    }
    
    void init()
    {
        fac[0] = inv[0] = 1;
        for(int i = 1;i < maxn;i++)
        {
            fac[i] = fac[i - 1] * i % mod;
            inv[i] = qpow(fac[i],mod - 2);
        }
    }
    
    ll C(ll n,ll m)
    {
        ll s1 = fac[n];
        ll s2 = inv[n - m];
        ll s3 = inv[m];
        return (s1 * s2) % mod * s3 % mod;
    }
    
    int cmp(P a,P b)
    {
        if(a.x == b.x)return a.y < b.y;
        return a.x < b.x;
    }
    
    int main()
    {
        init();
        ll h,w,n;
        cin >> h >> w >> n;
        for(int i = 1;i <= n;i++)
        {
            ll x,y;scanf("%lld%lld",&x,&y);
            p[i].x = x;p[i].y = y;
        }
        p[++n].x = h;p[n].y = w;
        sort(p + 1,p + 1 + n,cmp);
        for(int i = 1;i <= n;i++)
        {
            ll res = C(p[i].x + p[i].y - 2,p[i].x - 1);
            for(int j = 1;j < i;j++)
            {
                if(p[j].x > p[i].x || p[j].y > p[i].y)continue;
                res -= f[j] * C(p[i].x - p[j].x + p[i].y - p[j].y,p[i].x - p[j].x);
                res = (res + mod) % mod;
            }
            f[i] = (res + mod) % mod;
        }
        
        printf("%lld\n",f[n]);
        return 0;
    }
    
    
    
    • 1

    信息

    ID
    217
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    6
    已通过
    6
    上传者