about 4 years ago

問題來源:Codeforce Contest 472

總之,問題是:給定兩個等長序列,求第一個序列如何使用

的操作,來轉換成第二個序列

先假設序列一:,序列二:

這問題還頗有趣的,首先,可以把所有數字都當成的Vector,加法就是Xor。
那判斷性問題(判斷是否有解)就是在問,是否,證明的話很簡單,
這裡只提供一個想法:假如可以由某些步驟轉換成,那只要讓逆著步驟操作,
就可以變回,所以由生成的數字,必然也可在中找到。By 對稱,

下一步可以來看看Span的性質,首先,我們可以先把的Basis找出來,
怎麼找呢,只要在找就好了(由於裡的數字都可以由線性組合,
所以一定可以在裡面找到)。

的Basis也可以如此找出,由題目條件限制,可以知道Basis的大小不會超過

現在,我們令的Basis是的Basis是
我們用裡的元素一個一個送到(只要先把弄成,然後再做成就好啦),最後再把做成

其中有幾個很重要的問題

相同,Basis的大小必須相同,假如不同,套Replace Theorom可以幫比較小的Set補上一個數字,使的該Set仍然線性獨立。

如和把做成

想法大概是:
假設兩個Basis分別是:
那麼在裡面,必然存在一個一種線性組合
然後就把做出來了,然後用xor交換法,換到的位置。
再用歸納法,我們就把做成了。

← 三進位的位元操作? 我的第一個Online Judge →
 
comments powered by Disqus