UVa 13028 - XOR Subset

Source

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

問題概要

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

  1. $X \cap Y = \emptyset$
  2. $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$ のとき,同じと見なす.

解法

取り敢えず,$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: 2017年09月26日01時56分54秒
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)

ログイン: