CodeForces - 560E Gerald and Giant Chess dp+排列组合

传送门：https://codeforces.com/contest/560/problem/E

题意

给一个n*m的棋盘，想要从(1,1)走到(n,m)，但是又k个坏点不能经过，问有多少种方案？

思路

因为n和m都有1e5，所以不能f[i][j]，但是k只有2000，所以我们考虑坏点$O(n^2)$做法。

假如我们枚举到达坏点的方案，也可以将(n,m)这一点看出第k+1个坏点，所以考虑每两个坏点之间方案。

可以推出(x1,y1)走到(x2,y2)的方案为$C_{x_2-x_1+y_2-y_1}^{x_2-x_1}$。

所以从(1,1)出发到达的坏点有$C_{x+y-2}^{x-1}$。

设两个坏点为i和j，并且不能通过j到达i，所以要把到达i的方案减掉j到i的方案，即

$$dp[i]=dp[i]-dp[j]*\sum_{j=1}^{i-1}C_{p[i].x-p[j].x+p[i].y-[j].y}^{p[i].x-p[j].x}$$

这样一直枚举下去，ans=dp[k+1]，即到达最后一个坏点(n,m)的方案数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
##include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

 const ll mod = 1e9 + 7;

const int N = 2e5 + 10;

ll F[N], inv[N], invF[N];

void init() {
    F[0] = inv[0] = invF[0] = F[1] = inv[1] = invF[1] = 1;
    for(int i = 2;i < N; i++) {
        F[i] = F[i - 1] * i % mod;
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        invF[i] = invF[i - 1] * inv[i] % mod;
    }
}

ll C(int m, int n) {
    if(m < 0  n < 0  m < n) return 0;
    ll ans = F[m];
    ans = ans * invF[n] % mod;
    ans = ans * invF[m - n] % mod;
    return ans;
}

bool cmp(pll a, pll b) {
    if(a.first == b.first) return a.second < b.second;
    return a.first < b.first;
}

void solve()  {
    init();
    int n, m, k; cin >> n >> m >> k;
    vector<ll> dp(k + 10);
    vector<pll> p(k + 10);
    for(int i = 1;i <= k; i++) cin >> p[i].first >> p[i].second;
    sort(p.begin() + 1, p.begin() + k + 1, cmp);
    p[++k].first = n; p[k].second = m;
    for(int i = 1;i <= k; i++) {
        dp[i] = C(p[i].first + p[i].second - 2, p[i].first - 1);
        for(int j = 1;j < i; j++) { // j到i
            if(p[i].first >= p[j].first && p[i].second >= p[j].second) {
                // int temp = C(p[i].first - p[j].first + p[i].second - p[j].second, p[i].first - p[j].first);
                dp[i] = (dp[i] - dp[j] * C(p[i].first - p[j].first + p[i].second - p[j].second, p[i].first - p[j].first) % mod) % mod;
            }
        }
    }
    cout << (dp[k] % mod + mod) % mod << endl;
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/05/07/codeforces-560e-gerald-and-giant-chess/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！