2019-2020 ICPC Asia Taipei-Hsinchu Regional Contest

L - Largest Quadrilateral

题意：二维平面上给定 n 个点，求最大的四边形的面积。

旋转卡壳

四边形的对角线必定在凸包上，枚举对角线。对于一条对角线，两边各找出面积最大的三角形。

旋转卡壳求最大三角形。

当对角线旋转时，三角形的最大高度也同样方向旋转，所以可以旋转卡壳。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cout << #x << ":\t" << x << endl;
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
struct Point
{
	ll x, y;
	Point() {}
	Point(ll x, ll y) :x(x), y(y) {}
	Point operator+(Point p) {
		return Point(x + p.x, y + p.y);
	}
	Point operator-(Point p) {
		return Point(x - p.x, y - p.y);
	}
	Point operator*(ll d) {
		return Point(x*d, y*d);
	}
	ll dot(Point p) {
		return x * p.x + y * p.y;
	}
	ll cross(Point p) {
		return x * p.y - y * p.x;
	}
};
bool cmp_x(const Point& p, const Point& q) {
	if (p.x != q.x)return p.x < q.x;
	return p.y < q.y;
}
vector<int>convex_hull(Point* ps, int n, int flg = 1) {
	sort(ps, ps + n, cmp_x);
	int k = 0;
	vector<int>qs(n * 2);
	for (int i = 0; i < n; i++) {
		while (k > 1 && (ps[qs[k - 1]] - ps[qs[k - 2]]).cross(ps[i] - ps[qs[k - 1]]) < flg)k--;
		qs[k++] = i;
	}
	for (int i = n - 2, t = k; i >= 0; i--) {
		while (k > t && (ps[qs[k - 1]] - ps[qs[k - 2]]).cross(ps[i] - ps[qs[k - 1]]) < flg)k--;
		qs[k++] = i;
	}
	qs.resize(k - 1);
	return qs;
}
ll area(Point a, Point b, Point c) {
	return abs((a - b).cross(a - c));
}
ll rotating_calipers(vector<Point>& ps, int n) {
	ll res = 0;
	for (int i = 0; i < n; i++) {
		int p1 = (i + 1) % n;
		int p2 = (i + 3) % n;
		for (int j = (i + 2) % n; (j + 1) % n != i; j = (j + 1) % n) {
			while ((p1 + 1) % n != j && area(ps[p1], ps[i], ps[j]) < area(ps[(p1 + 1) % n], ps[i], ps[j])) {
				p1 = (p1 + 1) % n;
			}
			if (p2 == j)p2 = (p2 + 1) % n;
			while ((p2 + 1) % n != i && area(ps[p2], ps[i], ps[j]) < area(ps[(p2 + 1) % n], ps[i], ps[j])) {
				p2 = (p2 + 1) % n;
			}
			res = max(res, area(ps[p1], ps[i], ps[j]) + area(ps[p2], ps[i], ps[j]));
		}
	}
	return res;
}
int T;
int n;
Point p[N];
vector<int> ps;
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			scanf("%lld%lld", &p[i].x, &p[i].y);
		}
		ps = convex_hull(p, n, 0);
		int m = (int)ps.size();
		if (m < 3) {
			puts("0");
		}
		else if (m == 3) {
			ll ans = inf;
			for (int i = 0; i < n; i++) {
				if (i == ps[0] || i == ps[1] || i == ps[2])continue;
				ans = min(ans, area(p[i], p[ps[0]], p[ps[1]]));
				ans = min(ans, area(p[i], p[ps[0]], p[ps[2]]));
				ans = min(ans, area(p[i], p[ps[1]], p[ps[2]]));
			}
			ans = area(p[ps[0]], p[ps[1]], p[ps[2]]) - ans;
			if (ans & 1)printf("%lld.5\n", ans / 2);
			else printf("%lld\n", ans / 2);
		}
		else {
			vector<Point>pp;
			for (int i : ps)pp.push_back(p[i]);
			ll ans = rotating_calipers(pp, m);
			if (ans & 1)printf("%lld.5\n", ans / 2);
			else printf("%lld\n", ans / 2);
		}
	}
	return 0;
}

M - DivModulo

题意：定义 n dmod d，分解 $n=m\cdot d^h$ ，n dmod d = m % d. 给定 n，m，d，求 $C(n,m)$ dmod d.

中国剩余定理+Lucus定理

我们知道对于数 $n$ ，质数 $p$ ，可以计算出 $n!\equiv a\cdot p^e$ 。（挑战程序设计竞赛P293）

但是本题中 $D$ 不一定时质数。需要分解为质数的幂次的乘积，再应用中国剩余定理求解。

令 $D=p_1^{up_1}\cdot p_2^{up_2}\cdots p_{tot}^{up_{tot}}$ 。

记 $x\backslash p$ 表示从 $x$ 中除去所有 $p$ 的幂次后剩余结果。

对于每一个 $p_i$ ，有

$\begin{align} C_n^m &= \frac{n!}{m!\cdot(n-m)!}\\ &= \frac{(n!\backslash p_i)}{(m!\backslash p_i)\cdot ((n-m)!\backslash p_i)}\cdot p_i^{k_i}\\ \end{align}$

这样可以得到 $C_n^m$ 中包含的 $p_i$ 的幂次 $k_i$ 。

$n!$ 中包含的 $p$ 的幂次一定大于等于 $m!$ 和 $(n-m)!$ 中包含的 $p$ 的幂次之和，所以 $k_i\ge 0$ 。

$\lfloor\frac{k_i}{up_i}\rfloor$ 的最小值就是 $C_n^m$ 中包含的 $D$ 的幂次。记为 $K$ 。

由 dmod 的定义，有

$\begin{align} ans &= C_n^m\quad dmod \quad D\\ &= C_n^m\backslash D \mod D\\ &= \frac{(n!\backslash p_i)}{(m!\backslash p_i)\cdot ((n-m)!\backslash p_i)}\cdot (\frac{1}{D/p_i^{up_i}})^K\cdot p_i^{k_i-K\cdot up_i}\mod D\\ \end{align}$

再由中国剩余定理分解得到

$\begin{align} ans &= \frac{(n!\backslash p_i)}{(m!\backslash p_i)\cdot ((n-m)!\backslash p_i)}\cdot (\frac{1}{D/p_i^{up_i}})^K\cdot p_i^{k_i-K\cdot up_i}\mod p_i^{up_i}\\ \end{align}$

在这个线性同余方程组中，分母都与模互质，可以求逆元。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cout << #x << ":\t" << x << endl;
const int N = 2e7 + 10;
const int INF = 0x3f3f3f3f;
ll n, m, d;
int tot;
ll p[100], up[100], c[100], v[100], k[100], K, g[N];
ll count(ll n, ll p) {
	ll res = 0;
	while (n) {
		res += n / p;
		n /= p;
	}
	return res;
}
ll exgcd(ll a, ll b, ll& x, ll& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	ll t = exgcd(b, a%b, x, y);
	ll tmp = x;
	x = y;
	y = tmp - (a / b)*y;
	return t;
}
ll Pow(ll a, ll b, ll mod) {
	ll res = 1;
	while (b) {
		if (b & 1)res = res * a%mod;
		a = a * a%mod;
		b >>= 1;
	}
	return res;
}
ll inv(ll a, ll mod) {
	return Pow(a, mod - 2, mod);
}
ll mm[100], rr[100];
ll crt(ll* m, ll* r, ll n) {
	if (!n)return 0;
	ll M = m[0], R = r[0], x, y, d;
	for (int i = 1; i < n; i++) {
		d = exgcd(M, m[i], x, y);
		if ((r[i] - R) % d)return -1;
		x = (r[i] - R) / d * x % (m[i] / d);
		R += x * M;
		M = M / d * m[i];
		R %= M;
	}
	return R >= 0 ? R : R + M;
}
ll mod_fac(ll n, ll pi, ll di) {
	if (n == 0)return 1;
	return Pow(g[di - 1], n / di, di)*g[n%di] % di*mod_fac(n / pi, pi, di) % di;
}
int main() {
	scanf("%lld%lld%lld", &n, &m, &d);
	ll x = d;
	for (ll i = 2; i*i <= x; i++) {
		if (x%i == 0) {
			p[++tot] = i;
			v[tot] = 1;
			while (x%i == 0) {
				up[tot]++;
				x /= i;
				v[tot] *= i;
			}
		}
	}
	if (x != 1) {
		p[++tot] = x;
		v[tot] = x;
		up[tot] = 1;
	}
	K = INF;
	for (int i = 1; i <= tot; i++) {
		k[i] = count(n, p[i]) - count(m, p[i]) - count(n - m, p[i]);
		if (k[i] < 0)while (1);
		K = min(K, k[i] / up[i]);
	}
	for (int i = 1; i <= tot; i++) {
		mm[i - 1] = v[i];
		g[0] = 1;
		for (int j = 1; j < v[i]; j++) {
			g[j] = g[j - 1];
			if (j%p[i])g[j] = g[j] * j%v[i];
		}
		ll a1 = mod_fac(n, p[i], v[i]), a2 = mod_fac(m, p[i], v[i]), a3 = mod_fac(n - m, p[i], v[i]);
		k[i] -= K * up[i];
		rr[i - 1] = a1 * inv(a2, v[i]) % v[i] * inv(a3, v[i]) % v[i] * Pow(p[i], k[i], v[i]) % v[i] * inv(Pow(d / v[i], K, v[i]), v[i]) % v[i];
	}
	printf("%lld\n", crt(mm, rr, tot));
	return 0;
}