ARC124 参加記録 - geam1113’s diary

「全ての数字を必ず配置する」という条件があるので、制約iで指定された $k_i$ には必ずiを配置する必要があります。逆に、 $k_i$ にiを置くことにすれば、全ての数字を配置するという条件は満たされます。

ここで、K>Nなら答えは0です。以下、K≦Nとします。ここで、 $i \neq j \Rightarrow k_i \neq k_j$ という制約があるので、配置方法は必ず1通り以上存在します。

Lであればそれより右側にはiを0個以上配置でき、Rのときはそれが左側について成り立ちます。各制約について、iが配置可能なカードに+1ずつカウントしていきます。各カードに配置する数字の選び方は他のカードとは独立なので、各カードのカウント数の総積をとればそれが答えです。

重要な事実として以下があります。

$A\ XOR \ B\ XOR\ B = A$

これは同じ数で2回XORをとると、その値による影響がなくなるということを意味します。

この事実から、xが固定されれば、bの各要素について

$x\ XOR \ b_i=y$ を満たすyがaに一意に存在するか判定していけばよくなります。

xの候補は、aの要素のうち１つを固定し、bの各要素とのXORを全探索すればよいです。

WAをたくさん出してしまいましたが、1番はまったのが、条件を満たすxのうち、重複する要素を削除していなかったことでした。

頻出の考え方として「gcdの候補は約数」があり、今回はそれを適用できます。

$a_1$ を赤い袋、 $b_1$ を青い袋に入れることにすると、赤い袋と青い袋のgcdの組みとしてあり得るのは[ $a_1$ の約数の個数]×[ $b_1$ の約数の個数]通りに限定されます。

ここで、この組み合わせが最大何通りあるか見積もります。

「10^9以下の高度合成数の約数の個数は1344個」という事実があります。

従って、全ての組を全探索しても10^6程度です。

約数の組(x,y)が固定されれば、各 $a_i,\ b_i$ がx,yのいずれかを約数に持つかどうかを判定し、gcdをとっていくことで、(x,y)の組が実現できるか $O(Nlog(max(a_i,b_i)))$ で判定できます。

従って、約数を列挙する部分を除き、最悪でも $O({(1344)}^2Nlog(max(a_i,b_i))$ )でざっくり10^8程度となり、実行時間制限4 secに間に合いそうなのがわかります。

(本番では、実行時間制限を最初見ていなくて、途中で気がつきました)