BZOJ 4676 两双手

开始把 Ax 理解成了可以走任意A的倍数

首先,假设我们想从 $(0,0)$ 到达某个点 $(X,Y)$ ,第一种操作用了 $a$ 次,第二种用了 $b$ 次,那么有

由 zzh 胎教时期就会的数学知识,我们知道 $a,b$ 可以被解出来。

如果没有障碍点,我们就做完了,显然你只需要做个可重排列就完事了。

然后考虑,现在我们可以把第一种操作看成 $x+1$,第二种操作看成 $y+1$。

现在考虑障碍点这个问题。我们考虑枚举第一个经过的障碍点是谁。然后问题就是,求到达每个障碍点的方案数,并不经过其他障碍点。这个可以排序后容斥一下,枚举障碍点,枚举一个它左下角的障碍点。如果按照 $x$ 坐标第一关键字, $y$ 第二关键字排序,那么显然这个点左下角的点一定比它先被计算。注意,这里可以这么算是因为我们把原来的坐标变换已经变成了 $+1$ 操作。

然后就做完了。

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
76
77
78
79
80
81
82
83
84
85
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 1000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
#define P 1000000007
int n , m , ex , ey , ax , ay , bx , by;
pii poi[MAXN];
int J[MAXN] , iJ[MAXN];
int Pow( int x , int a ) {
int ret = 1;
while( a ) {
if( a & 1 ) ret = 1ll * ret * x % P;
x = 1ll * x * x % P , a >>= 1;
}
return ret;
}
inline int det( int a , int b , int c , int d ) {
return ( a * d - b * c );
}
int t;
inline int wkr( int X , int Y , int& a , int& b ) {
a = det( X , bx , Y , by ) , b = det( ax , X , ay , Y );
if( a % t || b % t ) return 0;
a /= t , b /= t; return 1;
}
int f[MAXN];
int A[MAXN] , B[MAXN];
int wy( int x , int y ) {
return J[x + y] * 1ll * iJ[x] % P * iJ[y] % P;
}
void solve() {
J[0] = 1;
rep( i , 1 , MAXN - 1 ) J[i] = 1ll * J[i - 1] * i % P;
iJ[MAXN - 1] = Pow( J[MAXN - 1] , P - 2 );
per( i , MAXN - 2 , 0 ) iJ[i] = 1ll * iJ[i + 1] * ( i + 1 ) % P;
cin >> ex >> ey >> n;
cin >> ax >> ay >> bx >> by;
t = det( ax , bx , ay , by );
rep( i , 1 , n ) {
scanf("%d%d",&poi[i].fi,&poi[i].se);
wkr( poi[i].fi , poi[i].se , poi[i].fi , poi[i].se );
}
poi[n + 1] = mp( ex , ey );
wkr( poi[n + 1].fi , poi[n + 1].se , poi[n + 1].fi , poi[n + 1].se );
sort( poi + 1 , poi + n + 1 );
int x , y;
rep( i , 1 , n + 1 ) {
x = poi[i].fi , y = poi[i].se;
if( x < 0 || y < 0 ) continue;
f[i] = wy( x , y );
if( !f[i] ) continue;
rep( j , 1 , i - 1 ) if( f[j] && x >= poi[j].fi && y >= poi[j].se ) {
f[i] += P - 1ll * f[j] * wy( x - poi[j].fi , y - poi[j].se ) % P , f[i] %= P;
}
}
cout << f[n + 1] << endl;
}

signed main() {
// freopen("input","r",stdin);
// freopen("fuckout","w",stdout);
// int T;cin >> T;while( T-- ) solve();
solve();
}

文章作者: yijan
文章链接: https://yijan.co/bzoj-4676-liang-shuang-shou/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog