UVa 13028 - XOR Subset

Source

An Asian Preliminary Regional（20151205）
(ICPC Dhaka 2015 Preliminary)
UVa 13028

問題概要

$1$ から $N$ までの整数からなる集合を $S$ とする．
$X, Y \subseteq S$ を以下の $2$ 条件を満たすように定める．

$X \cap Y = \emptyset$
$X$ のすべての要素の $\mathrm{XOR}$ は $Y$ のすべての要素の $\mathrm{XOR}$ 以下である

条件を満たす $(X,Y)$ の数を $\mathrm{MOD}\ 1000000007\ (10^9+7)$ で求める問題．
ただし，$2$ つのサブセットの組 $(X_1,Y_1), (X_2,Y_2)$ は $X_1=X_2, Y_1=Y_2$ または $X_1=Y_2, Y_1=X_2$ のとき，同じと見なす．

テストケースの数 $T$ は $T \leq 100$ を満たす
$0 \leq N < 10^{100000}$

解法

取り敢えず，$X \cap Y = \emptyset$ ならば，$\mathrm{XOR}$ が小さい方を $X$，大きい方を $Y$ とすれば，条件を満たすものが作れる．
同じと見なす条件が変なので，$\mathrm{XOR}$ が等しい場合も，同じとみなされるので $1$ つしかできない．
よって，$X=Y=\emptyset$ の $1$ パターンと，そうでない $3^N - 1$ パターンのうちの半分が条件を満たすを思って良い．
答えは $(3^N + 1) / 2$ になる．

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります．

Current time: 2024年04月20日03時11分53秒
Last modified: 2015年12月16日01時02分30秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151205_1
トップページに戻る

Logged in as: unknown user (not login)