BZOJ 4767: 两双手

Description

老W是个棋艺高超的棋手，他最喜欢的棋子是马，更具体地，他更加喜欢马所行走的方式。

老W下棋时觉得无聊，便决定加强马所行走的方式，更具体地，他有两双手，其中一双手能让马从$(u,v)$移动到$(u+A_x,v+A_y)$而另一双手能让马从$(u,v)$移动到$(u+B_x,v+B_y)$。小W看见老W的下棋方式，觉得非常有趣，他开始思考一个问题：假设棋盘是个无限大的二维平面，一开始马在原点$(0,0)$上，若用老W的两种方式进行移动，他有多少种不同的移动方法到达点$(E_x,E_y)$呢？两种移动方法不同当且仅当移动步数不同或某一步所到达的点不同。老W听了这个问题，觉得还不够有趣，他在平面上又设立了$n$个禁止点，表示马不能走到这些点上，现在他们想知道，这种情况下马有多少种不同的移动方法呢？答案数可能很大，你只要告诉他们答案模$(10^9+7)$的值就行。

Input

第一行三个整数$E_x,E_y,n$分别表示马的目标点坐标与禁止点数目。第二行四个整数$A_x,A_y,B_x,B_y$分别表示两种单步移动的方法，保证$A_x * B_y-A_y * B_x\neq 0$接下来n行每行两个整数$S_{x_i},S_{y_i}$，表示一个禁止点。

Output

仅一行一个整数，表示所求的答案。

Sample Input

Sample Output

1
40

Constraint

20%的数据：0 <= Ax,Ay,Bx,By <= 10 30%的数据：n <= 10 另有10%的数据：n <= 15, Ax=1, Ay=0, Bx=0, By=1 另有10%的数据：n=0 另有20%的数据：n=1 另有10%的数据：n=2 100%的数据：|Ax|,|Ay|,|Bx|,|By| <= 500, 0 <= n,Ex,Ey <= 500

Source

BZOJ 十连测推广赛

Solution

动态规划解决计数问题。

先旋转坐标系，dp[i]表示不经过1..i-1的点到达第i个点的方案数。

定义calc(x,y)表示从原点向右或者向上走到(x,y)的方案数。

则dp[i] = calc(x[i], y[i]) - Sum dp[j] * calc(x[i]-x[j], y[i]-y[j])

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int getint() { int r = 0; bool b = true; char c = getchar(); while ('0' > c || c > '9') {if (c == '-') b = false; c = getchar();} while ('0' <= c && c <= '9') {r = (r<<3) + (r<<1) + (c-'0'); c = getchar();} if (b) return r; return -r; }
const LL P = 1000000007ll;
LL tx, ty, ax, ay, bx, by, sx, sy, frac[1000005], frav[1000005], dp[505];
int n;
inline LL ksm(LL a, LL b, LL P) {
    LL ret = 1ll, tmp = a;
    while (b) {
        if (b & 1ll) ret = (ret * tmp) % P;
        tmp = (tmp * tmp) % P;
        b >>= 1ll;
    }
    return ret;
}
inline LL C(int n, int m) { return frac[n] * frav[m] % P * frav[n-m] % P; }
inline LL calc(LL x, LL y) { return C(x + y, x); }
vector<pair<LL, LL> > v;
inline void fu(LL tx, LL ty) {
    LL Y = (tx*ay-ax*ty)/(bx*ay-by*ax); if (Y * (bx*ay-by*ax) != (tx*ay-ax*ty)) return;
    LL X = (ty*bx-tx*by)/(bx*ay-by*ax); if (X * (bx*ay-by*ax) != (ty*bx-tx*by)) return;
    if (X < 0 || Y < 0) return;
    v.push_back(make_pair(X, Y));
}
int main() {
    v.clear();
    frac[0] = 1ll; for (int i = 1; i <= 1000000; ++i) frac[i] = frac[i-1] * LL(i) % P;
    frav[1000000] = ksm(frac[1000000], P - 2ll, P); for (int i = 999999; i >= 0; --i) frav[i] = frav[i+1] * LL(i+1) % P;
    tx = getint(); ty = getint(); n = getint();
    ax = getint(); ay = getint(); bx = getint(); by = getint();
    int i, j;
    for (i = 0; i < n; ++i) {
        sx = getint();
        sy = getint();
        fu(sx, sy);
    }
    sort(v.begin(), v.end());
    fu(tx, ty);
    for (i = 0; i < v.size(); ++i)
        for (j = 0, dp[i] = calc(v[i].first, v[i].second); j < i; ++j)
            if (v[j].first <= v[i].first && v[j].second <= v[i].second)
                dp[i] = (dp[i] - dp[j] * calc(v[i].first - v[j].first, v[i].second - v[j].second) % P + P) % P;
    printf("%lld", dp[v.size() - 1]);
    fclose(stdin); fclose(stdout); return 0;
}