AT_tupc2024_c 2-Power Rush

正整数の多重集合が **良い集合** であるとは、含まれる要素がすべて $ 2 $ べきであることをいいます。 非負整数 $ N $ に対して、要素の総和が $ N $ であるような良い集合それぞれについて要素の総積を計算したとき、それらの総和を $ f(N) $ とします。ただし、空集合の要素の総和は $ 0 $ 、総積は $ 1 $ として $ f(0)=1 $ とします。 非負整数 $ T,a,b $ が与えられます。 $ N_i=(ai+b)\ \mathrm{mod}\ 2^{30} $ としたとき、 $ \displaystyle \sum_{i=0}^{T-1}(f(N_i)\ \mathrm{mod}\ 998244353)\oplus i $ を求めてください。 ここで、 $ \oplus $ はビットごとの排他的論理和です。 ビットごとの排他的論理和とは 非負整数 $ A,B $ のビットごとの排他的論理和 (XOR) $ A \oplus B $ は、以下のように定義されます。 - $ A \oplus B $ を二進表記した際の $ 2^k \, (k \geq 0) $ の位の数は、 $ A,B $ を二進表記した際の $ 2^k $ の位の数のうち一方のみが $ 1 $ であれば $ 1 $ 、そうでなければ $ 0 $ である。 例えば、 $ 3 \oplus 5 = 6 $ となります (二進表記すると: $ 011 \oplus 101=110 $ )。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ a $ $ b $

答えを出力せよ。

### 部分点 この問題には複数の部分点が設定されている。 - 追加の制約 $ T\leq 10^6,a=1,b=0 $ を満たすデータセットに正解した場合は $ 10 $ 点が与えられる。 - 追加の制約 $ T\leq 1000 $ を満たすデータセットに正解した場合は $ 10 $ 点が与えられる。 ### Sample Explanation 1 $ N_0=0,N_1=1,N_2=2,N_3=3,N_4=4 $ です。 - 総和が $ 0 $ である良い集合は $ \lbrace\rbrace $ であり、 $ f(0)=1 $ です。 - 総和が $ 1 $ である良い集合は $ \lbrace1\rbrace $ であり、 $ f(1)=1 $ です。 - 総和が $ 2 $ である良い集合は $ \lbrace1,1\rbrace,\lbrace2\rbrace $ であり、 $ f(2)=(1\times 1)+(2)=3 $ です。 - 総和が $ 3 $ である良い集合は $ \lbrace1,1,1\rbrace,\lbrace1,2\rbrace $ であり、 $ f(3)=(1\times 1\times 1)+(1\times 2)=3 $ です。 - 総和が $ 4 $ である良い集合は $ \lbrace1,1,1,1\rbrace,\lbrace1,1,2\rbrace,\lbrace2,2\rbrace,\lbrace4\rbrace $ であり、 $ f(4)=(1\times 1\times 1\times 1)+(1\times 1\times 2)+(2\times 2)+(4)=11 $ です。 よって、求める答えは $ (1\oplus 0)+(1\oplus 1)+(3\oplus 2)+(3\oplus 3)+(11\oplus 4)=17 $ です。 ### Sample Explanation 2 $ N_0=1000000000,N_1=926258176,N_2=852516352 $ です。 ### Constraints - $ 1\leq T\leq 10^7 $ - $ 0\leq a,b\lt 2^{30} $ - 入力は全て整数