凳子充分地让我切身实地地体会到了平行四边形的不稳定性。做题的时候可以 360° 无死角地把下半身转来转去，有点意思。也有点容易摔（×
A. 两双手
http://222.180.160.110:1024/contest/3506/problem/1
不难发现可以通过解二元一次方程组得到用几个 A 操作和 B 操作才能让横纵坐标分别改变一些特定的值。可惜我没能想到一个经典的容斥 DP 思想：
定义起点为点 \(0\)。定义 \(C(x,y)\) 表示从 \(x\) 点走到 \(y\) 点的方案数（可经过特殊点）。对于特殊点 \(1\sim n\)，顺序枚举，对于点 \(i\)，定义 \(f_i\) 表示从 \(0\sim i\) 不经过任何除 \(i\) 以外的特殊点的方案数，则 \(f_i=C(0,i)-\sum\limits_{j=1}^{i-1}f_j\times C(j,i)\)。其中 \(\sum\limits_{j=1}^{i-1}f_j\times C(j,i)\) 就是从 \(0\) 到 \(i\)，除 \(i\) 以外经过至少 1 个特殊点的方案数。用总方案数减去不合法方案数，则得到合法方案数。
一个细节。我们枚举时，可能会遇到只能从 \(i\) 到达 \(j\)，而不能从 \(j\) 到达 \(i\) 的情况。若恰好 \(j\) 在 \(i\) 前面，那么从 \(i\) 到 \(j\) 的路径就会被统计漏。这个时候怎么办呢？对于任意点 \(i\)，我们求得从 \(0\to i\) 所需的步数，并以此为关键字从小到大排序，那么我们就能保证，任意一条合法路径都会被我们统计到。
namespace XSC062 {
using namespace fastIO;
#define mkp std::make_pair
using pii = std::pair<int, int>;
const int lim = 1e6;
const int maxn = 505;
const int mod = 1e9 + 7;
const int maxm = 1e6 + 5;
struct _ { int x, y, w; };
std::set<pii> t;
_ s[maxn], s1[maxn];
int fac[maxm], f[maxn];
int ex, ey, n1, n, ax, ay, bx, by;
inline int gcd(int x, int y) {
return y ? gcd(y, x % y) : x;
}
inline int lcm(int x, int y) {
return x / gcd(x, y) * y;
}
pii Solve(int a, int b, int c,
int d, int e, int f) {
int N = 0, M = 0;
if (!a) {
if (c % b)
return mkp(-1, -1);
M = c / b, f -= M * e;
if (f % d)
return mkp(-1, -1);
N = f / d;
}
else if (!b) {
if (c % a)
return mkp(-1, -1);
N = c / a, f -= N * d;
if (f % e)
return mkp(-1, -1);
M = f / e;
}
else if (!d) {
if (f % e)
return mkp(-1, -1);
M = f / e, f -= M * b;
if (c % a)
return mkp(-1, -1);
N = c / a;
}
else if (!e) {
if (f % d)
return mkp(-1, -1);
N = f / d, c -= N * a;
if (c % b)
return mkp(-1, -1);
M = c / b;
}
else {
int g = lcm(b, e);
a *= g / b, c *= g / b, b = g;
d *= g / e, f *= g / e, e = g;
if ((c - f) % (a - d))
return mkp(-1, -1);
N = (c - f) / (a - d), c -= N * a;
if (c % b)
return mkp(-1, -1);
M = c / b;
}
return mkp(N, M);
}
inline int qkp(int x, int y) {
int res = 1;
while (y) {
if (y & 1)
(res *= x) %= mod;
(x *= x) %= mod;
y >>= 1;
}
return res;
}
inline int inv(int x) {
return qkp(x, mod - 2);
}
inline int A(int n, int m) {
return (fac[n] * inv(fac[n - m])) % mod;
}
inline int C(int n, int m) {
return (A(n, m) * inv(A(m, m))) % mod;
}
inline void Init(void) {
fac[0] = 1;
for (int i = 1; i <= lim; ++i)
fac[i] = (fac[i - 1] * i) % mod;
return;
}
int main() {
read(ex), read(ey), read(n1);
read(ax), read(ay), read(bx), read(by);
for (int i = 1; i <= n1; ++i) {
read(s1[i].x), read(s1[i].y);
pii t = Solve(ax, bx, s1[i].x,
ay, by, s1[i].y);
s1[i].w = t.first + t.second;
}
std::sort(s1 + 1, s1 + n1 + 1,
[&](_ x, _ y) { return x.w < y.w; });
Init(), f[0] = 1, ++n1;
s1[n1].x = ex, s1[n1].y = ey;
for (int i = 1; i <= n1; ++i) {
pii t = Solve(ax, bx, s1[i].x,
ay, by, s1[i].y);
if (t.first < 0 || t.second < 0) {
if (i == n1) {
puts("0");
return 0;
}
continue;
}
s[++n] = s1[i];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
pii t = Solve(ax, bx, s[i].x
- s[j].x, ay, by, s[i].y
- s[j].y);
if (t.first < 0 || t.second < 0)
continue;
(f[i] += (f[j] * C(t.first +
t.second, t.first)) %
mod) %= mod;
}
pii t = Solve(ax, bx, s[i].x,
ay, by, s[i].y);
f[i] = (C(t.first + t.second,
t.first) + mod - f[i]) % mod;
}
print(f[n]);
return 0;
}
} // namespace XSC062
B. 绮丽的天空
http://222.180.160.110:1024/contest/3506/problem/2
标签：230418,return,int,归档,补题,fac,mkp,inline,mod From： https://www.cnblogs.com/XSC062/p/17330225.html