【题解】GYM-102129A-Tritwise Mex
题目
2018-2019 Winter Petrozavodsk Camp, Oleksandr Kulkov Contest 1
题意
\(C_k = \sum_{mex_3(i,j)=k} A_i B_j\),其中 \(mex_3\) 是三进制意义下按位取 \(mex\)(其中 \(mex(x,y)\) 的值等同于和 \(x\) 以及 \(y\) 都不相等的最小非负整数)。
题解
官方题解可以在这里找到。
- 首先要会 FWT,可以参考这个。
- 然后把这个写出来,其实写一下那个 \(mex\) 的值的表格会更清楚。
\[ \begin{eqnarray} c_0 &=& a_1b_2 + a_2b_1 + a_1b_1 + a_2b_2\\ c_1 &=& a_0b_0 + a_0b_2 + a_2b_0 \\ c_2 &=& a_0b_1 + a_1b_0 \end{eqnarray} \]
- 然后开始凑(目标用 \(c\) 就是凑出完全一直的两个关于 \(a\) 和 \(b\) 的式子的积),发现只能凑出前两个,于是不得不加两项,还搞出了一个 \(c_3\)。
\[ \begin{eqnarray} c_0 &=& (a_1+a_2)(b_1+b_2) \\ c_0 + c_1 + c_2 &=& (a_0 + a_1 + a_2)(b_0 + b_1 + b_2) \\ c_3 &=& a_2b_2 \\ c_1 + c_3 &=& (a_0 + a_2)(b_0 + b_2) \end{eqnarray} \]
- 然后就仿照 FWT,但是现在是一个四进制的问题,首先把原来的三进制转成四进制,如果有一位的值是 3 的话那就是多出来的,系数是无所谓。再补充一下,大概就是三进制转四进制然后求积最后在转回三进制。
代码(这里放的是一份会 MLE 的代码。强行卡空间的代码太难看了就不放了。另外,SB 出题人卡内存。)
1 |
|