問題一覧 > 通常問題

No.1410 A lot of Bit Operations

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 29
作問者 : 👑 PCTprobabilityPCTprobability / テスター : akakimidoriakakimidori hotman78hotman78
4 ProblemId : 5600 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-02-26 22:34:25

問題文

上の表の $x,y,z,w$ に $0,1$ のどちらかを入れ、非負整数 $a,b$ の各bitに対して上の表を使うという演算を $S_{x+2y+4z+8w}$ と定義します。 例えば、$S_6$ は $a,b$ のbitが違う時は $1$、同じときは $0$ なのでXORのことです。

正整数 $N$ と全ての文字がoか-である $8$ 文字の文字列 $K$ が与えられます。 $0$ 以上 $7$ 以下かつ $K_{i+1}$ が o である非負整数 $i$ に対して以下の値を合計を $1000000007$ で割った余りを出力してください。

$0$ 以上 $2^N$ 未満の非負整数の組 $(P,Q,R)$ であって、$((P$ $S_i$ $Q )-R)×((P$ $S_{15-i}$ $Q) -R) \le 0$ を満たすものの数。ただし、それぞれの演算の計算結果はちょうど $N$ 桁となるようleading-zeroをいれて計算してください。(21:45 追記)

入力

$N$
$K$

  • $N$ は整数である。
  • $K$ は全ての文字がoか-の文字列である。
  • $0 \le N \le 10^{18}$
  • $|K|=8$

出力

問題文に書かれている値を出力してください。

サンプル

サンプル1
入力
3
-o------
出力
368

演算 $S_1$ とはnor演算のことです。演算 $S_{14}$ とはnor演算をした後に ! 演算をすると同値です。 例えば、$(P,Q,R)=(4,6,4)$ などが条件を満たします。

サンプル2
入力
4736175978463
o--o-oo-
出力
942654651

$N$ の制約に注意してください。また解を $1000000007$ で割った余りを求めることに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。