No.1800 Random XOR
タグ : / 解いたユーザー数 169
作問者 :
NatsubiSogan
/ テスター :
penguinman
Cyanmond
問題文
正の整数 $N,M$ が与えられます。
数列 $A=(A_1,A_2,\dots,A_N)$ を以下のように決定します。
- 各 $i$ $(1 \leq i \leq N)$ について、$A_i$ は $0$ 以上 $2^M-1$ 以下の整数から一様ランダムに選ばれる。この選択は他の要素とは独立である。
$A_1 \oplus A_2 \oplus \dots \oplus A_N$ の期待値を $\bmod 10^9+7$ で出力してください（注記参照）。ただし、$a \oplus b$ は $a,b$ の排他的論理和を表します。
注記
この制約下で、求める期待値は有理数になります。これを既約分数 $\displaystyle \frac{P}{Q}$ とすると、$Q \not \equiv 0 \pmod{10^9+7}$ となることが証明できます。このもとで、$R \times Q \equiv P \pmod{10^9+7}$ なる $0$ 以上 $10^9+7$ 未満の整数 $R$ が一意に定まるので、$R$ を出力してください。
入力
$N$ $M$
- 入力はすべて整数
- $1 \leq N,M \leq 10^{18}$
出力
$A_1 \oplus A_2 \oplus \dots \oplus A_N$ の期待値を $\bmod 10^9+7$ で出力してください。
最後に改行してください。
サンプル
サンプル1
入力
2 1
出力
500000004
- $A_1=0,\ A_2 = 0$ のとき：$A_1 \oplus A_2 = 0$
- $A_1=0,\ A_2 = 1$ のとき：$A_1 \oplus A_2 = 1$
- $A_1=1,\ A_2 = 0$ のとき：$A_1 \oplus A_2 = 1$
- $A_1=1,\ A_2 = 1$ のとき：$A_1 \oplus A_2 = 0$
なので、求める期待値は $\displaystyle \frac{1}{2}$ です。これを $\bmod 10^9+7$ で表現すると、$500000004$ となります。
サンプル2
入力
314159265358979323 271828182845904523
出力
803876782
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。