1 条题解
-
0
自动搬运
来自洛谷，原作者为
zhoukangyang
^w^/搬运于
2025-08-24 22:26:38，当前版本为作者最后更新于2021-01-21 16:15:53，作者可能在搬运后再次修改，您可在原文处查看最新版自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多
以下是正文
验题验不动，就来写写题解吧
/qq在本文中，我们让 （即三角形面积的 次方之和） 。此题拓展到 也是没问题的
首先要求的是 三个点围成的三角形面积 的和，我们显然要快速求出这个东西。
运用计算机和知识，或在百度上搜第一篇就可以找到答案 ：
三个点 围成的三角形面积为 ： $\frac{1}{2} |x_1 y_2 + x_2 y_3 + x_3 y_1 - x_1 y_3 - x_2 y_1 - x_3 y_2|$
对于每一个三角形，可以把这个三角形算 次。
我们要计算的就是 $\frac{1}{6} \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{n} \sum\limits_{k = 1}^{n} (\frac{1}{2} |x_i y_j + x_j y_k + x_k y_i - x_i y_k - x_j y_i - x_k y_j|)^8$
（把有相同的点的也算进去了，这东西算出的答案为 ，对答案没有贡献）
$$\frac{1}{6 \times 2^8} \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{n} \sum\limits_{k = 1}^{n} (x_i y_j + x_j y_k + x_k y_i - x_i y_k - x_j y_i - x_k y_j)^8 $$用二项式定理的拓展把后面的一堆东西展开：
$$\frac{1}{1536} \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{n} \sum\limits_{k = 1}^{n} \sum\limits_{a + b + c + d + e + f = 8} \binom{8}{a, b, c, d, e, f} (x_i y_j)^a (x_jy_k)^b (x_k y_i)^c (-x_iy_k)^d (-x_jy_i)^e (-x_ky_j)^f $$$$\frac{1}{1536} \sum\limits_{a + b + c + d + e + f = 8} (-1)^{d+e+f} \binom{8}{a, b, c, d, e, f} \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{n} \sum\limits_{k = 1}^{n}x_i^a y_j^a x_j^by_k^b x_k^cy_i^c x_i^dy_k^d x_j^ey_i^e x_k^fy_j^f $$$$\frac{1}{1536} \sum\limits_{a + b + c + d + e + f = 8} (-1)^{d+e+f} \binom{8}{a, b, c, d, e, f} (\sum\limits_{i = 1}^{n} x_i^{a+d} y_i^{c+e}) (\sum\limits_{j = 1}^{n} x_j^{b+e} y_j^{a+f}) (\sum\limits_{k = 1}^{n} x_k^{c+f} y_k^{b+d}) $$这样对于每一个 和 维护 ，统计答案时 一下就是 的了。事实上那个 会很小，是
轻微卡常可以通过。
代码：
#include<bit/stdc++.h> #define L(i, j, k) for(int i = j, i##E = k; i <= i##E; i++) #define R(i, j, k) for(int i = j, i##E = k; i >= i##E; i--) #define ll long long #define ull unsigned long long #define db double #define pii pair<int, int> #define mkp make_pair using namespace std; const int N = (1 << 20); const int M = 10; const int mod = 998244353; int qpow(int x, int y = mod - 2) { int res = 1; for(; y; x = (ll) x * x % mod, y >>= 1) if(y & 1) res = (ll) res * x % mod; return res; } int n, k = 8, inv1536; int sum[M][M], f[M], ifac[M], fac[M]; ll ans; void dfs(int x, int w, int now) { if(x == 6) { f[x] = w, now = (ll) now * ifac[w] % mod; int res = (ll) now * sum[f[1] + f[4]][f[3] + f[5]] % mod * sum[f[2] + f[5]][f[1] + f[6]] % mod * sum[f[3] + f[6]][f[2] + f[4]] % mod; if((f[4] + f[5] + f[6]) & 1) res = mod - res; ans += res; return; } L(i, 0, w) f[x] = i, dfs(x + 1, w - i, (ll) now * ifac[i] % mod); } int mian() { inv1536 = qpow(1536); scanf("%d", &n); fac[0] = ifac[0] = 1; L(i, 1, k) fac[i] = (ll) fac[i - 1] * i % mod, ifac[i] = qpow(fac[i]); L(i, 1, n) { int opt, x, y; scanf("%d%d%d", &opt, &x, &y); int now = 1; L(a, 0, k) { int Now = now; L(b, 0, k) { if(opt == 1) (sum[a][b] += Now) %= mod; else (sum[a][b] += mod - Now) %= mod; Now = (ll) Now * y % mod; } now = (ll) now * x % mod; } ans = 0, dfs(1, k, 1); printf("%lld\n", (ll) ans % mod * fac[k] % mod * inv1536 % mod); } return; }这样的常数十分不优良，考虑预处理出来要计算的每一次要调用的 的下标和乘上的系数。
这样子常数原来的 。
对于每一次调用的 数组，有很多本质相同的，于是考虑把他们压缩起来。把相同的调用系数加起来就好了。
这样子常数减小到了最初的
（细节见代码）
#include<bits/stdc++h> #define L(i, j, k) for(int i = j, i##E = k; i <= i##E; i++) #define R(i, j, k) for(int i = j, i##E = k; i >= i##E; i--) #define ll long long #define ull unsigned long long #define db double #define pii pair<int, int> #define mkp make_pair using namespace std; const int M = 10; const int P = 5000; const int mod = 998244353; int qpow(int x, int y = mod - 2) { int res = 1; for(; y; x = (ll) x * x % mod, y >>= 1) if(y & 1) res = (ll) res * x % mod; return res; } int n, k = 8, inv1536; int sum[M][M], f[M], ifac[M], fac[M]; struct node { int x, y; } ; bool operator < (node aa, node bb) { return aa.x == bb.x ? aa.y < bb.y : aa.x < bb.x; } bool operator == (node aa, node bb) { return aa.x == bb.x && aa.y == bb.y; } struct Node { int buf; node f[4]; } d[P], g[P]; bool operator < (Node aa, Node bb) { return aa.f[1] == bb.f[1] ? (aa.f[2] == bb.f[2] ? aa.f[3] < bb.f[3] : aa.f[2] < bb.f[2]) : aa.f[1] < bb.f[1]; } bool operator == (Node aa, Node bb) { return aa.f[1] == bb.f[1] && aa.f[2] == bb.f[2] && aa.f[3] == bb.f[3]; } int tot, all; ll ans; void dfs(int x, int w, int now) { if(x == 6) { f[x] = w, now = (ll) now * ifac[w] % mod, ++tot; d[tot].f[1].x = f[1] + f[4], d[tot].f[1].y = f[3] + f[5]; d[tot].f[2].x = f[2] + f[5], d[tot].f[2].y = f[1] + f[6]; d[tot].f[3].x = f[3] + f[6], d[tot].f[3].y = f[2] + f[4]; sort(d[tot].f + 1, d[tot].f + 4); if((f[4] + f[5] + f[6]) & 1) now = mod - now; d[tot].buf = (ll) now * inv1536 % mod * fac[k] % mod; return; } L(i, 0, w) f[x] = i, dfs(x + 1, w - i, (ll) now * ifac[i] % mod); } int main( { inv1536 = qpow(1536); scanf("%d", &n); fac[0] = ifac[0] = 1; L(i, 1, k) fac[i] = (ll) fac[i - 1] * i % mod, ifac[i] = qpow(fac[i]); dfs(1, 8, 1); sort(d + 1, d + tot + 1); L(i, 1, tot) { if(g[all] == d[i]) (g[all].buf += d[i].buf) %= mod; else ++all, g[all] = d[i]; } L(i, 1, n) { int opt, x, y; scanf("%d%d%d", &opt, &x, &y); int now = 1; L(a, 0, k) { int Now = now; L(b, 0, k) { if(opt == 1) (sum[a][b] += Now) %= mod; else (sum[a][b] += mod - Now) %= mod; Now = (ll) Now * y % mod; } now = (ll) now * x % mod; } ans = 0; L(j, 1, all) { (ans += (ll) sum[g[j].f[1].x][g[j].f[1].y] * sum[g[j].f[2].x][g[j].f[2].y] % mod * sum[g[j].f[3].x][g[j].f[3].y] % mod * g[j].buf % mod) %= mod; } printf("%lld\n", ans); } return 0;的时候本质不同的 数组调用次数为 ，在 的时候也只有 。
orz w33z
15011418730
LV 7
@ 2025-8-24 22:26:38
- 1
