No.3478 XOR-Folding Primes
タグ : / 解いたユーザー数 27
作問者 : 👑
loop0919
/ テスター :
ぽえ
遭難者
問題文
整数 $N, M$ が与えられます。
長さ $N$ の数列 $P = (P_1, P_2, \cdots, P_N)$ のうち、以下の条件をすべて満たすものの個数を $998244353$ で割った余りを求めてください。
- $P$ の各要素はすべて $M$ 以下の素数である。
- $1 \leq k \leq N$ なる任意の整数 $k$ について、$P_1 \oplus P_2 \oplus \cdots \oplus P_k$ は $M$ 以下の素数である。
ここで、$\oplus$ はビットごとの排他的論理和を表します。
$T$ 個のテストケースが与えられるので、それぞれについて答えてください。
ビットごとの排他的論理和 $\oplus$ とは（クリックで開く）
非負整数 $a, b$ のビットごとの排他的論理和 $a \oplus b$ は、以下のように定義されます。
- $a \oplus b$ を二進表記したときの $2^k ~ (k \ge 0)$ の位の数は、$a, b$ を二進表記したときの $2^k$ の位の数のうち一方のみが $1$ であれば $1$ 、そうでなければ $0$ である。
例えば、$3 \oplus 5 = 6$ となります（二進表記にすると $011 \oplus 101 = 110$ ）。
一般に $k$ 個の非負整数 $x_1, x_2, \cdots, x_k$ のビットごとの排他的論理和 $x_1 \oplus x_2 \oplus \cdots \oplus x_k$ は $(\cdots((x_1 \oplus x_2) \oplus x_3) \oplus \cdots \oplus x_k)$ と定義され、これは $x_1, x_2, \cdots, x_k$ の順番によらないことが証明できます。
制約
- $1 \leq T \leq 10^5$
- $1 \leq N \leq 10^9$
- $2 \leq M \leq 10^7$
- $M$ は素数である
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられます。ここで、$t$ 番目 $(1 \leq t \leq T)$ のテストケースを $\mathrm{case}_t$ と表します。
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
各テストケースは以下の形式で与えられます。
$N$ $M$
出力
$T$ 行出力してください。 $t$ 行目には $t$ 番目のテストケースについての答えを出力してください。
サンプル
サンプル1
入力
4 2 7 1 101 919 9461 1000000000 9999991
出力
6 26 63669221 862727226
$1$ 番目のテストケースについて、例えば $P = (2, 7)$ が条件を満たします。
- $k = 1$ のとき、$2$ は $M = 7$ 以下の素数です。
- $k = 2$ のとき、$2 \oplus 7 = 5$ は $M$ 以下の素数です。
このような数列が $6$ 個存在します。
$3$ 番目、 $4$ 番目のテストケースについて、$998244353$ で割った余りを求めることに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。