2015年12月16日01時02分30秒に更新されたバージョンを表示しています.
最新のページはこちらをご覧ください.
An Asian Preliminary Regional(20151205)
(ICPC Dhaka 2015 Preliminary)
UVa 13028
$1$ から $N$ までの整数からなる集合を $S$ とする.
$X, Y \subseteq S$ を以下の $2$ 条件を満たすように定める.
条件を満たす $(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$ になる.
この部分を表示するには表示権限を持つユーザーでログインする必要があります.
Current time: 2024年05月03日07時15分31秒
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)