Algoogle

Algorithm for Programming Contest

AOJ 2214 Warp Hall

Category: AOJ Tag: dp, math

Warp Hall

問題概要


格子上を(1,1)から(n,m)に移動するとき, その移動方法の数を求める.
ただし移動はy軸方向に+1するか, x軸方向に+1するかしかできない.
また途中に入口と出口が固定されたワープホールがあり, 入口の点からは出口の点にしか移動できない.

解法


始点からある点p(x,y)に到達する場合の数を考える.
まずワープホールがない場合pに到達するを数える(これは余裕).
pより左下にワープホールの入口wsが存在するとき, 始点->ws->pと移動するような場合の数が減る.
pより左下にワープホールの出口wtが存在するとき, 始点->ws->wt->pと移動するような場合の数が増える.
つまり始点からpに到達する場合の数は, 始点からwsに到達する場合の数がわかればよい.
よってワープホールをx座標, y座標の順(左下に来るものが先に来るよう)にソートしてDPをすればよい.

dp[i] := i番目のワープホールの入口に到達する場合の数

コード


(2214.cpp) download
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
inline int add(int a, int b) { return (a+b)%mod;}
inline int sub(int a, int b) { return (a-b+mod)%mod;}
inline int mul(int a, int b) { return 1LL*a*b%mod;}

struct warp
{
        int sx, sy, tx, ty;
        bool operator<(const warp &w) const {
                if(sx != w.sx) return sx < w.sx;
                return sy < w.sy;
        }
};

int extgcd(int a, int b, int &x, int &y)
{
        int g = a; x = 1; y = 0;
        if(b != 0) g = extgcd(b,a%b,y,x), y -= a/b*x;
        return g;
}
int inv(int a) {
        int x, y; extgcd(a,mod,x,y);
        return (mod+x%mod)%mod;
}
int fact[200010];
inline int nck(int n, int k) { return mul(mul(fact[n], inv(fact[n-k])), inv(fact[k]));}


int n, m, k, dp[100010];
// dp[i] := i番目のワープホールの入り口までの場合の数
vector<warp> warps;

inline int calc(int sx, int sy, int tx, int ty)
{
        if(tx < sx or ty < sy) return 0;
        return nck(tx-sx+ty-sy, tx-sx);
}

int solve()
{
        memset(dp,0,sizeof(dp));
        sort(begin(warps),end(warps));
        warps.push_back((warp){n,m, n+1, m+1});
        for (int i = 0; i <= k; i++) {
                dp[i] = nck(warps[i].sx+warps[i].sy, warps[i].sy);
                for (int j = 0; j < i; j++) {
                        dp[i] = add(dp[i], mul(dp[j], sub(calc(warps[j].tx, warps[j].ty, warps[i].sx,warps[i].sy),
                                                          calc(warps[j].sx, warps[j].sy, warps[i].sx,warps[i].sy))));
                }
        }
        return dp[k];
}

bool input()
{
        warps.clear();
        cin >> n >> m >> k;
        n--; m--;
        int a, b, c, d;
        for (int i = 0; i < k; i++) {
                cin >> a >> b >> c >> d;
                warps.push_back((warp){a-1,b-1,c-1,d-1});
        }
        return n+1 or m+1 or k;
}

int main()
{
        fact[0] = 1;
        for (int i = 0; i < 200000; i++) fact[i+1] = mul(fact[i], i+1);
        while(input()) cout << solve() << endl;
        return 0;
}

Comments