专栏文章

NOI 2025

GGalois_Field_1048576
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minrmcu4
此快照首次捕获于
2025/12/02 07:13
3 个月前
此快照最后确认于
2025/12/02 07:13
3 个月前
查看原文
均不转述题目.

D1T2

考虑一个经典 trick: 相邻相同位相抵 (例如, 反转, 缩去形如 aa\tt aa 的子串, 以及本题的同时减去 min⁡{x,y}\min \{x, y\}) 可以考虑奇数/偶数位反转
w(l,r)=∑k∈[l,r)(−1)kak.w (l, r) = \sum_{k \in [l, r)} (-1)^k a_k.
同时, 另一个经典的思考模式: 考虑如果我们一条路走到黑会发生什么. 因此我们考虑处理函数 L(l)L(l): 考虑一直让后面抵消前面, 即递推
Xl=Al,Xk=Ak−Xk−1.X_l = A_l, \quad X_k = A_k - X_{k - 1}.
这样对于最小的 Xr<0X_r < 0, 令 L(l)=rL(l) = r. 同理定义 R(r)R(r) 为
Xr−1=Ar−1,Xk=Ak−Xk+1X_{r-1} = A_{r-1}, \quad X_k = A_k - X_{k + 1}
对应的最小的 Xl≥0X_l \ge 0. 那么一个可达的区域 CC 可以定义为:
Push(l,r)=[ max⁡{l,R(r)},min⁡{r,L(l)} ).\mathrm{Push}(l, r) = \Big[\ \max \{l, R(r)\}, \min \{r, L(l)\}\ \Big).
则 Push(l,r)=∅\mathrm{Push}(l, r) = \varnothing 说明我们不能把 Al,…,Ar−1A_l, \dots, A_{r - 1} 的贡献推到一个 AmA_m 上, 反之亦然. 如果我们遇到 Push(l,r)=∅\mathrm{Push}(l, r) = \varnothing 说明我们应该把这个区间拆分, 因此我们着重研究 Push(l,r)≠∅\mathrm{Push}(l, r) \ne \varnothing. 我们来看一下 ww-不变量.
  • w(l,r)=0w(l, r) = 0: 这说明我们把 [l,r)[l, r) 推进到 p∈Push(l,r)p \in \mathrm{Push}(l, r) 时使得所有数在 pp 处相消. 显然这是一个充要条件, 因此 [l,r)[l, r) 能清空 ⇔w(l,r)=0\Leftrightarrow w(l, r) = 0.
  • 否则, 任取 p∈Push(l,r)p \in \mathrm{Push}(l, r), 不难看出 (−1)pApfinal=w(l,r),(-1)^p A^{\rm final}_p = w(l, r), 因此 w(l,r)>0⇔p≡0(mod2),w(l,r)<0⇔p≡1(mod2).\begin{aligned} w(l, r) > 0 \Leftrightarrow p \equiv 0 \pmod 2, \\ w(l, r) < 0 \Leftrightarrow p \equiv 1 \pmod 2. \end{aligned} 这提示我们应当考虑位置的奇偶性.
分段双射于所有可能操作. 具体地, I0⊔I1⊔⋯⊔Im−1={0,1,…,N−1}I_0 \sqcup I_1 \sqcup \dots \sqcup I_{m - 1} = \{0, 1, \dots, N-1\}, 并附带 pi∈Push(Ii)⊔{∗}p_i \in \mathrm{Push}(I_i) \sqcup \{*\} 满足 Push(Ii)≠∅\mathrm{Push}(I_i) \ne \varnothing, 且 w(Ii)=0w(I_i) = 0 时 pi=∗p_i = * 且 w(Ii)≠0w(I_i) \ne 0 时 pip_i 满足相应奇偶性要求, 这样的结构 R\mathcal R 双射于 T(A)T(A). 显然根据上文的铺垫我们有 R→T(A)\mathcal R \to T(A) 的一个自然映射. 现在我们证明它是一个双射.
  • 满射: 对于 Afinal∈T(A)A^{\rm final} \in T(A), 存在对应于其的一个操作序列 O\mathcal O, 则我们可以通过对 O\mathcal O 中每操作 (i,i+1)(i, i + 1) 则连边, 则连通分量为所求. (易证每个连通分量至多一个非 00);
  • 单射: 不难发现不同的操作序列给出不同的 T(A)T(A). 而不同的 R\mathcal R 给出不同的操作序列. 结论得证.
下面对于一个对加法成幺半群, 对乘法 (除了 00 以外) 成群的结构讨论.
现在考虑分段. 对于某一段 [l,r)[l, r), 只需考虑其对答案的贡献. 进而考虑对 sgn⁡w\operatorname{sgn}w 做分类讨论. 如果 w(I)=0w(I) = 0, 那么这一段的贡献显然是
∏i∈IWi.\prod_{i \in I} W_i.
否则, 显然是:
∑i∈I,i≡sgn⁡w(mod2)∏j≠iWj=(∑i∈I,i≡sgn⁡w(mod2)1Wi)∏i∈IWj.\sum_{i \in I, i \equiv \operatorname{sgn} w \pmod 2} \prod_{j \ne i} W_j = \left( \sum_{i \in I, i \equiv \operatorname{sgn} w \pmod 2} \dfrac 1{W_i} \right) \prod_{i \in I} W_j.
因此可以预处理后 Θ(N2)\Theta(N^2) 去做.
这题有点魔怔的点就在于入股哦你不想对同一件事写两份代码 (虽然写两份代码就是提截取的各位所做的), 那么你应该就要面临卡常. 先放一个卡常前的比较简洁的代码
CPP
enum block { split = -2, emptify = -1, parity_0 = 0, parity_1 = 1 };

auto blocking(u32 n, vector<i64>& a) {
    vector<i64> pre(n + 1), L(n + 1, n), R(n + 1);
    for (u32 i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i] * (i % 2 == 1 ? -1 : 1);
    for (u32 i = 0; i < n; i++) {
        i64 x = a[i];
        for (u32 j = i + 1; j < n && x > 0; j++) {
            x = a[j] - x;
            if (x < 0) L[i] = j;
            if (x == 0) L[i] = j + 1;
        }
    }
    for (u32 i = 0; i < n; i++) {
        i64 x = a[i];
        for (int j = i - 1; j >= 0 && x > 0; j--) {
            x = a[j] - x;
            if (x < 0) R[i + 1] = j + 1;
            if (x == 0) R[i + 1] = j;
        }
    }

    auto corridor = [L = move(L), R = move(R)](u32 l, u32 r) {
        return make_pair(max<u32>(l, R[r]), min<u32>(r, L[l]));
    };

    auto classify = [pre = move(pre), corridor](u32 l, u32 r) {
        auto [ll, rr] = corridor(l, r);
        if (ll >= rr) return split;
        if (pre[r] - pre[l] == 0) return emptify;
        if (pre[r] - pre[l] > 0) return parity_0;
        return parity_1;
    };

    return make_pair(corridor, classify);
}

template <class T>
T solve(u32 n, vector<i64>& a, vector<T>& weight) {
    auto [corridor, classify] = blocking(n, a);
    vector prod(n, vector<T>(n + 1, T::one()));
    for (u32 i = 0; i < n; i++) {
        prod[i][i + 1] = weight[i];
        for (u32 j = i + 1; j < n; j++) prod[i][j + 1] = prod[i][j] * weight[j];
    }
    vector<T> pweight = weight;
    for (auto& x : pweight) x = x.inv();
    vector parity(n, vector<array<T, 2>>(n + 1, {T::zero(), T::zero()}));

    for (u32 i = 0; i < n; i++) {
        for (u32 p : {0, 1})
            if (i % 2 == p) parity[i][i + 1][p] = pweight[i];
        for (u32 j = i + 1; j < n; j++) {
            for (u32 p : {0, 1}) parity[i][j + 1][p] = parity[i][j][p];
            parity[i][j + 1][j % 2] = parity[i][j][j % 2] + pweight[j];
        }
    }
    auto calc = [&](u32 l, u32 r) {
        auto typ = classify(l, r);
        if (typ == split) return T::zero();
        if (typ == emptify) return prod[l][r];
        auto [ll, rr] = corridor(l, r);
        return prod[l][r] * parity[ll][rr][typ];
    };

    vector<T> dp(n + 1, T::zero());
    dp[0] = T::one();
    for (u32 i = 1; i <= n; i++)
        for (u32 j = 0; j < i; j++) dp[i] = dp[i] + dp[j] * calc(j, i);
    return dp[n];
}
卡常技巧就是把 prod 和 parity 当做数组指针传进去, 然后注意到 n2×6n^2 \times 6 大概是 1 100 MB1\ 100\ \rm MB, 所以你可以给 (+,×)(+, \times) 上 int 类型然后转 i64. 这很魔怔吧!

D1T3

发现答案是 2M2^M, 考虑线性代数. 假设所有点是 V=I⊔LV = I \sqcup L, 所有颜色是 CC. 可以看出所有 DFS 序对应一个反转方案, 而一个反转方案是 F2I\mathbb F_2^I 的向量. 我们定义 b(v)b(v) 表示 [v 是优美的][v\ \text{是优美的}]. 首先考虑刻画它. 考虑一个颜色 cc 的分歧位置 vv, 满足 vv 的左边含一个 cc, 右边含一个 cc. 如果把 LuL_u 和 RuR_u 的可消部分消掉, 那么剩下的部分一定形如 u | uR\tt u\ \texttt{|}\ u^R. 现在考虑按照某种方式消颜色, 那么考虑
dp(parent)=dp(l)+dp(r)∈F2C.{\rm dp(parent)} = {\rm dp}(l) + {\rm dp}(r) \in \mathbb F_2^{\it C}.
发现 dp\rm dp 相等的点应当匹配, 它们的反转 b(v)b(v) 应当有偶数个翻转位置. 当然, 如果 dp\rm dp 是平凡的 (这里的平凡指 Hamming 权重 ≤1\le 1), 那么反不反转是一致的, 不构成约束.
考虑证明. 不妨设 uu 就是根 (我们可以取一个适当的子树满足这一点).

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...