ビット列を並べる Clojure(Beta)編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
整数 N が与えられます。
以下のすべての条件を満たす数列の個数を求めてください。
・数列の要素数が 1 以上
・数列の各要素が 1 以上 N 以下
・数列の要素数を L としたとき、1 ≦ i ＜ j ≦ L について常に「i 番目の要素の popcount ＜ j 番目の要素のpopcount」(popcount は 2 進数表記に含まれる 1 の個数)
ただし、値が非常に大きくなる場合があるため、条件を満たす数列の個数を 998244353 で割った余りを出力してください。
- 入力される値
-
入力は以下のフォーマットで与えられます。i
N
・1 行目には 整数 N が与えられます。
・入力は合計で 1 行からなり、入力値最終行の末尾に改行が１つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
条件を満たす数列の個数を 998244353 で割った余りを出力してください。
最後は改行し、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N ≦ 1000000
- 入力例1
-
5
- 出力例1
-
11
- 入力例2
-
33
- 出力例2
-
11087
