問題一覧 > 通常問題

No.1800 Random XOR

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 121
作問者 : NatsubiSoganNatsubiSogan / テスター : CyanmondCyanmond penguinmanpenguinman
3 ProblemId : 7036 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-17 20:13:34

問題文

正の整数 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。