傳送門

題意：有一序列$S$由下列方式生成：

找到字典序最小的正整數(shù)$(a,b,c)$，滿足$a,b,c$不在$S$中且$a\oplus b\oplus c=0$,其中$\oplus$為異或

將$a,b,c$加入$S$

重復第一步

$T$組數(shù)據(jù)，求$S$的第$n$項。

$T\le 10^5,n\le 10^{16}$

通過觀察樣例和理性猜想，可以假設(shè)前$4^k?1$項恰好填完了$1～4^k?1$，顯然這是整數(shù)個三元組。采用歸納法構(gòu)造$4^k～4^{k+1}?1$

將每個序列中的數(shù)按二進制位兩個為一組拆分（以下稱拆成的兩個二進制位為"位"），當前的數(shù)(已構(gòu)造的和此步將構(gòu)造的)有$2(k+1)$位

之前填的$4^k?1$項可以看成最高位為$\text{00}$，我們要構(gòu)造的是最高位為$\text{01,10,11}$，后面$k$位分別遍歷$0～4^k?1$

對于每一個$(a,b,c)$顯然有$a<b<c$

構(gòu)造$a$最高位為$\text{01}$,容易得到$b,c$最高位為$\text{10,11}$。這是最理想的結(jié)果，下面將證明這種構(gòu)造是可行的。

現(xiàn)在已經(jīng)滿足了$a<b<c$，那么$a,b,c$的后$k$位是互不影響的。下面討論的都是這后$k$位。

現(xiàn)在考慮如何最小化字典序

對于一個已經(jīng)確定的$a$，我們都需要找到最小的$b$(廢話)

對于$a$上的每一位，都找到一個最小的對應(yīng)的$b$的位即可（似乎還是廢話，但似乎就是想不到）

設(shè)新構(gòu)造的三元組為$(a_i,b_i,c_i)(0\le i\le 2^k?1)$顯然所有的$a_i=i$

根據(jù)以上信息可以構(gòu)造出$(a,b,c)$每一位字典序最小的對照表

盜用官方題解的圖：

隨便推一下就可以了

復雜度$O(T\log n)$

總結(jié)

以上是生活随笔為你收集整理的【CF1338C】Perfect Triples【位运算】【构造】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。