GDKOI2023游寄

· · 个人记录

可能更好的阅读体验

day1

T1:给出三个 n\times n 的矩阵 A,B,C，判断是否 C=A\times B，对 998,244,353取模。\\多组数据，\sum n\leq3,000

T2:求有几个 1\sim n 的排列 p，满足 \forall 1\leq i\leq m,p_i>m 且 \forall 1\leq i\leq n,p_i\not=i，对 998,244,353取模。\\多组数据，t\leq2\times10^5,0\leq m\leq n\leq2\times10^5。

T3：给一个 n 点 m 边无向图、长度为 n 的序列 a 和一个常数 C，求有几个整数点权序列 b_i 满足:\\\forall i,0\leq b_i\leq a_i\\\forall (u,v)\in G,b_u\not = b_v\\\operatorname{xor}_{i=1}^n b_i=C\\答案对 998,244,353取模\\1\leq n\leq15,0\leq C,a_i\leq 10^{18}

先用了大概 30min 看完题，之后还是觉得 T1 应该更适合先开。

想到显然不能直接求矩阵乘法，就试着去写几个类似匹配的式子来计算，我写了个式子：

\sum\limits_{i=1}^n\sum\limits_{j=1}^n (C_{i,j}-\sum\limits_{k=1}^nA_{i,k}B_{k,j})^2 \pmod{998,244,353}

但是会出现 \sum\limits_{i=1}^n\sum\limits_{j=1}^n\sum\limits_{k=1}^nC_{i,j}A_{i,k}B_{k,j} 的式子，很快就弃了。

于是我就想用哈希来解决，取一个小质数 p(10^8\leq p<10^9)，设矩阵 C 的哈希值为：

\sum\limits_{i=1}^n\sum\limits_{j=1}^n C_{i,j}p^{in+j} \mod 998,244,353

那么 A\times B的哈希值就是：

\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sum\limits_{k=1}^nA_{i,k}B_{k,j} p^{in+j} =\sum\limits_{k=1}^n(\sum\limits_{i=1}^nA_{i,k}p^{in})(\sum\limits_{j=1}^nB_{k,j} p^{j})

但是我很愚蠢地用了 NTT，加上对拍成功写了2h呢。

开 T2 时已经只剩 1.5h 了，容斥一下p_i=i的个数可以得到式子：

ans=\begin{pmatrix}n-m\\m\end{pmatrix}m!\sum\limits_{i=0}^{n-2m}(-1)^{n-2m-i}\begin{pmatrix}n-2m\\i\end{pmatrix}(i+m)!

推出式子出来的时候已经不到 1h 了，所以我就把 T\leq10 和 n\leq5,000 的部分分写了，期望 60 分。

开 T3，急急急，写了暴力 20 分就差不多结束了。

期望得分 100+60+20=180，实际得分相同。

T1 正解是随机一个 1\times n 的矩阵 v，判断是否 v\times A\times B=v\times C

T2 是把 O(n^2) 的dp用生成函数推式子

T3 是容斥

day2

T1:给一颗 n 点的树，q 次查询 x,y,z，构造三元组 (u,v,w) 满足 dis(u,v)=x,dis(u,w)=y,dis(v,w)=z。\\n,q\leq2\times10^5

T2:给一个数 x 和一个长度为 2^n 的整数序列 c，做 K 次操作，每次操作随机一个整数 y\in[0,2^n)，p 的概率让 x\leftarrow x \operatorname{or} y，1-p 的概率让 x\leftarrow x \operatorname{and} y\\设序列 a 的权值为 \sum\limits_{i=1}^K c_{a_i}，求生成的 x 组成的序列的权值的期望，对 998,244,353 取模。\\ 1\leq n\leq17,1\leq K\leq10^9,0\leq p,c_i<998,244,353

T3:给一颗 n 点的树，带点权，q 次查询 x,k，求式子： \sum\limits_{dis(x,y)\leq k} dis(x,y) \operatorname{xor} v_y。\\1\leq n,q\leq 10^6

先花了半小时看题，之后还是开 T1：

一般情况下三条路径只有一个公共点，设为p，可以解方程得到 dis(p,u),dis(p,v),dis(p,w)。

考虑预处理每个 p 能拉出的前三长链，预处理之后解决询问就是三维偏序，期望 100 分。

写完 T1 已经只剩 1.5h了，T2有个显然的 O((2^{n+1})^3\log K) 的矩阵快速幂优化 dp 做法，但是这个只能过 n=1 的部分分。

补充：有个 n\leq 8 的部分分，但是显然过不去，不理解出题人在干啥。

之后又考虑写个暴力转移，发现要枚举子集，是 O(K3^n) 的，然后还过不去 K\leq20 的部分分，稍稍卡了卡常，应该能过。期望得分 [10,30]。

还剩下 1h 做 T3。想了一会儿正解，但没想到。只好打了 O(nq) 的暴力，最后想到 v_i=0 的部分分应该可以线段树合并做，但是来不及了，期望得分 10 分。

期望得分：100+[10,30]+10=[110,140]，实际成绩20+0+10=30挂麻了。

D2T1拍了几十组大数据还是挂了80分(官方提供了spj)。

总结

好像尽力了，又好像没尽力。

D1T3 完全没写过 dp套dp等骗分的东西，而且 D1T2 因为太急了，根本没有考虑后面怎么做。（虽然标算的 O(n\sqrt {n\log n}) 也挺离谱的）

D2T1 估计是救不回来，拍了很多组大数据，而且一共花了1.5h了，确实不好接着多拍一会儿，而且至今还不知道哪里错了。

D2T2 不知道为啥两个部分分都没分，O(K3^n) 有可能还是卡不过去，n=1 的可能矩阵快速幂某个地方写挂了吧。

估计还是太菜了。

还有，一道sb题对拍了还挂大分真的很搞心态，真不好说啥。

谢谢你，GDKOI2023，让我获得了我该有的耻辱。