题解 P7101 【[w3R1] 推】

zhoukangyang · 2021-01-21 16:15:53 · 题解

更好的阅读体验 /kel /kel

验题验不动，就来写写题解吧 /qq

在本文中，我们让 k = 8 （即三角形面积的 k 次方之和） 。此题拓展到 k = 16 也是没问题的

首先要求的是 三个点围成的三角形面积 的和，我们显然要快速求出这个东西。

运用计算机和知识，或在百度上搜第一篇就可以找到答案 ：

三个点 (x_1, y_1), (x_2, y_2), (x_3, y_3) 围成的三角形面积为 ： \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|

对于每一个三角形，可以把这个三角形算 6 次。

我们要计算的就是 \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

（把有相同的点的也算进去了，这东西算出的答案为 0，对答案没有贡献）

用二项式定理的拓展把后面的一堆东西展开：

这样对于每一个 A 和 B 维护 sum(A, B) = \sum\limits_{i = 1}^{n} x_i^A y_i^B，统计答案时 dfs 一下就是 \Theta(k^5 n) 的了。事实上那个 k^5 会很小，是 \binom{k+5}{5}

轻微卡常可以通过。

代码：

#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;
}

这样的常数十分不优良，考虑预处理出来要计算的每一次要调用的 sum 的下标和乘上的系数。

这样子常数原来的 \frac{1}{2}。

对于每一次调用的 sum 数组，有很多本质相同的，于是考虑把他们压缩起来。把相同的调用系数加起来就好了。

这样子常数减小到了最初的 \frac{1}{12}

（细节见代码）

#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;