Solution -「GLR-R4」大暑

· · 题解

\mathscr{Description}

  [Link]().

  这里有兔以前写的另一个题意，大家可以参考着看看。

  你有两个坐标集合 X,Y，X=\{(0,y)\mid y\in[0,n)\cap\mathbb N\}，Y=\{(1,y)\mid y\in[0,n)\cap\mathbb N\}。

  现在你需要将 X 中每个点与 Y 中每个点配对构成双射，将它们连接。配对完成后，你需要从 X 的每个点 (0,k) 出发，沿着配对的线，走一条线段或折线到达 Y 中一点，并为走过的线涂上第 k 种颜色。你需要保证走动过程的任意时刻，x 轴方向的速度 v_x 为正。

  染色完成后，你需要保证任意线段上的任意一个不与其他线段相交的点都恰好被染上一种颜色。

  对于一种配对方案，令其权值为染色方案数。求所有配对方案的权值之积，模 335544323。

  m\le10^6。

\mathscr{Solution}

  Subtask 1 (n\le9) 不妨称第 i 个点阵图内部的染色方案数为排列 \sigma_i 的权值，记为 v(\sigma_i)。我们自然是要求所有排列权值之积。

  如果不会算 v(\sigma_i) 那确实只能过 n\le4 了（因为 n=4 是样例）。仔细一想，其实 v(\sigma_i) 很容易求出——对于点阵图中一个被 k 条线段通过的点 P，有 k 种颜色可以在这个点上任意交换，贡献因子为 k!。所以 v(\sigma_i) 就是所有这样的 k! 的乘积。

  知道这一点，直接 std::next_permutation，\mathcal O(n!\operatorname{poly}(n)) 就能拿到这档分。

 

  Subtask 2 (n\le100) 注意 v(\sigma_i) 是若干阶乘的乘积，而答案又是所有 v(\sigma_i) 的乘积，所以可以独立地计算每个 k! 对答案的贡献。

  通过枚举两条线段交点，获得一个至少被两条线段经过的点 P，再枚举得到可能经过 P 的线段总数 l，精细实现可以在 \mathcal O(n^4\operatorname{polylog}(n)) 的时间内完成这一步。

  此后，我们预处理 w(l) 表示最多可能 l 条线段经过的点对答案的总贡献。枚举实际经过该点的线段数量，容斥求出这一情况下排列的数量，可以得到

w(l)=\prod_{i=2}^li!^{\binom{l}{i}\sum_{j=0}^{l-i}(-1)^j\binom{l-i}{j}(n-i-j)!}.

  暴力计算即可。注意指数应该对 \varphi(p)=p-1 取模。

 

  Subtask 3/4 (n\le500~/~n\le5\times10^3) 求 w(l) 并不是瓶颈，来看看如何加速 P 的枚举。令 c(l) 表示得到线段总数为 l 的 P 的数量。那么答案可以表示为：

\textit{ans}=\prod_{l=2}^nw(l)^{c(l)}.

  注意到，若已知两直线 l_1,l_2 过 x=0 和 x=1 中间的任意一点 P，则 l_1,l_2,l:x=0 围成的三角形 \triangle_1 与 l_1,l_2,l:x=1 围成的三角形 \triangle_2 的相似比是一定的。换言之，若在 x=0 上取 y 升序排列的点 A_{0..k}，在 x=1 上取 y 降序排列的点 B_{0..k}，且所有直线 A_iB_i 交于一点时，必然存在唯一常数 k，使得 \forall i\neq j,~|A_iA_j|:|B_iB_j|=k。

  利用这一结论，我们来进一步刻画一个交点 P 被理论最多的交线经过的情况。通过直观感受不难注意到，若存在某个 i，使得 y_{A_{i+1}}-y_{A_i}\neq y_{A_i}-y_{A_{i-1}}，不妨设 y_{A_{i+1}}-y_{A_i}>y_{A_{i}}-y_{A_{i-1}}，那么我们再取一个 A(0,y_{A_i}+(y_{A_i}-y_{A_{i-1}}))，对应地有 B(1,y_{B_i}-(y_{B_{i+1}}-y_{B_i}))，可以验证 AB 过 P，这与 |\{A_k\}|,|\{B_k\}| 的最大性矛盾。因此，\{A_k\},\{B_k\} 中的点的纵坐标应当分别为等差数列。

  再进一步，设 \{A_k\} 中纵坐标的公差为 d_1~(d_1>0)，\{B_k\} 中纵坐标的公差为 d_2~(d_2>0)。显然，|\{A_k\}|,|\{B_k\}| 的最大性还需要满足：

  2. 在保证 y\in[1,n] 的情况下，y_{A_{0..k}} 与 y_{B_{k..0}} 无法同时依各自公差向后延伸。否则可以延伸出更多整点。

  第 2 个要求听上去比较麻烦，先不管它。令 t(l) 表示交线数量为 l，忽略要求 2 时最大集合对 (\{A\},\{B\}) 的数量。那么

t(l)=\sum_{d_1\perp d_2,\\d_1,d_2\le n/(l-1)}(n-d_1(l-1))(n-d_2(l-1)).

  进行一个小巧的容斥。对于任意一个可能不合法的 (\{A_{k+1}\},\{B_{k+1}\})，其必然对应两个一定不的合法 (\{A_k\},\{B_k\})；对于一个不合法的 (\{A_k\},\{B_k\})，若等差数列可以向两种方向一起延伸，则其对应一个可能不合法 (\{A_{k+1}\},\{B_{k+1}\})，否则对应两个可能不合法的 (\{A_{k+1}\},\{B_{k+1}\})。因而

c(l)=t(l)-2t(l+1)+t(l+2).

  随便乱算一下可以 \mathcal O(n^2) 过掉子任务 3,4，但如果带 \log 被卡常或者写得实在太丑就只有子任务 3 啦。

 

  Subtask 5 (n\le10^5) 一步步来优化。对于 c(l)，也即 t(l)，利用众所周知的结论

\sum_{i\le n}[i\perp n]i=\frac{1}{2}(\operatorname{id}\cdot\varphi+\epsilon)(n),

可以化出 \mathcal O(n) 的式子。不过这不是瓶颈，所以也大可以 \mathcal O(n\log n) 莫反算。即

t(l)=\sum_{d=1}^{n/(l-1)}\mu(d)\sum_{d_1=1}^{n/(l-1)/d}\sum_{d_2=1}^{n/(l-1)/d}(n-dd_1(l-1))(n-dd_2(l-1)).

  从最终答案入手。最终答案为

\begin{aligned} \textit{ans} &= \prod_{l\ge2}w(l)^{c(l)}\\ &= \prod_{l\ge2}\prod_{i\le l}i!^{c(l)\binom{l}{i}\sum_{j=0}^{l-i}(-1)^j\binom{l-i}{j}(n-i-j)!}\\ &= \prod_{i=2}^ni!^{\sum_{l\ge i}c(l)\binom{l}{i}\sum_{j=0}^{l-i}(-1)^j\binom{l-i}{j}(n-i-j)!}. \end{aligned}

  记 f(i) 为 i! 的那一大坨指标，那么

\begin{aligned} f(i) &= \sum_{l\ge i}c(l)\binom{l}{i}\sum_{j=0}^{l-i}(-1)^j\binom{l-i}{j}(n-i-j)!\\ &= \sum_{l\ge i}c(l)\sum_{j=0}^{l-i}(-1)^j(n-i-j)!{\color{red}{\binom{l}{i}\binom{l-i}{j}}}\\ &= \sum_{l\ge i}c(l)\sum_{j=0}^{l-i}(-1)^j(n-i-j)!{\color{red}{\binom{l}{i+j}\binom{i+j}{i}}}\\ &= \sum_{j=0}^n(-1)^j(n-i-j)!\binom{i+j}{i}{\color{blue}{\sum_{l\ge i+j}c(l)\binom{l}{i+j}}}~~~~(*)\\ &= \sum_{j=0}^n(-1)^j(n-i-j)!\binom{i+j}{i}{\color{blue}{g(i+j)}}\\ &= \frac{1}{i!}\sum_{j=0}^n\frac{(-1)^j}{j!}\cdot(n-i-j)!(i+j)!g(i+j). \end{aligned}

  其中 (*) 的最后一个和式是关于 l 与 l-(i+j) 的差卷积，\mathcal O(n\log n) 卷出来得到 g(i+j)。最后 f 的形式又是关于 i+j 和 j 的差卷积，因而可以 \mathcal O(n\log n) 求解。

  还没完，p=335544323，p-1 显然不可能是素数，而且还有超小因子 2，式子里又有 \frac{1}{i!} 这种东西。这怎么卷？放弃了放弃了，随便整点多项式玄学凑合一下。希望能过这档。

 

  Subtask 6 (n\le10^6) 这怎么卷？——天依可是精心挑选了一个有趣的模数！

  注意到 p-1=2\times 167772161，因子很少，尝试 CRT 合并出 f 模 p-1 的结果。对于后者，167772161=5\times2^{25}+1 是个 NTT 模数，可以直接算；对于前者，观察最初的式子：

f(i) = \sum_{l\ge i}c(l)\binom{l}{i}\sum_{j=0}^{l-i}(-1)^j\binom{l-i}{j}(n-i-j)!.

  不去动组合数，整个式子没有除法。因而当 n-i-j>1 时 2\mid (n-i-j)!，对答案没有影响。所以 j 只可能取 n-i 和 n-i-1。相应地，l\ge i+j 也少得可怜，所以可以 \mathcal O(1) 算出 f(i)\bmod 2。本题就 \mathcal O(n\log n) 完成啦。

\mathscr{Code}

/*+Rainybunny+*/

#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)
#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)

const int MAXN = 1e6, MR = 335544323, MP = 167772161, MC = MR - 1;
int n, c[MAXN + 5], g[MAXN + 5], f[MAXN + 5];
int h[MAXN + 5]; // a temp poly.
int fac[MAXN + 5], ifac[MAXN + 5], pn, pr[MAXN + 5], mu[MAXN + 5];
bool npr[MAXN + 5];

namespace Basic {

} using namespace Basic;

namespace Poly {

} // namespace Poly.

inline void sieve() {

}

inline void init() {

}

int main() {
    scanf("%d", &n);
    Poly::init(), sieve(), init();

    rep (l, 2, n) {
        rep (d, 1, n / (l - 1)) if (mu[d]) { // can be O(n).
            int a = repd / d;
            int s = (((n - d * (l - 1ll))
              + (n - a * d * (l - 1))) * a >> 1) % MC;
            addeqC(c[l], mulC(mu[d], mulC(s, s)));
        }
    }
    rep (l, 2, n) c[l] = subC(addC(c[l], c[l + 2]), mul(2, c[l + 1]));

    rep (i, 0, n) h[i] = ifac[i];
    rep (i, 0, n) g[i] = mul(fac[i], c[i] % MP);
    Poly::polyMulT(n + 1, g, h, g);
    rep (i, 0, n) g[i] = mul(g[i], ifac[i]);

    rep (i, 0, n) h[i] = i & 1 ? sub(0, ifac[i]) : ifac[i];
    rep (i, 0, n) g[i] = mul(mul(fac[n - i], fac[i]), g[i]);
    Poly::polyMulT(n + 1, g, h, f);
    rep (i, 0, n) f[i] = mul(f[i], ifac[i]);

    rep (i, 2, n) {
        int s = 0;
        rep (j, n - i - (i < n), n - i) {
            rep (l, i + j, n) {
                s += c[l] & 1 && (l | i) == l && ((l - i) | j) == l - i;
            }
        }
        if ((s & 1) != (f[i] & 1)) f[i] += MP; // mod MC.
    }

    fac[0] = 1;
    rep (i, 1, n) fac[i] = mulR(i, fac[i - 1]); // mod MP initially.
    int ans = 1;
    rep (i, 2, n) ans = mulR(ans, mpowR(fac[i], f[i]));
    printf("%d\n", ans);
    return 0;
}