競技プログラミング用 知識集積所
ABC406E - Popcount Sum 3
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
ゴリゴリの数学問題。
与えられるnの値が2の累乗より1小さい値であれば話は簡単である。
例えばn=31でk=2の場合、5ビットの中で2か所に1を置くパターンは10通りある。
それぞれのビットで見れば、10通りのうちの2/5にあたる4通りでそこに1がある。
つまり、(16+8+4+2+1)*10*(2/5)=124が答えである。
例えばn=31でk=2の場合、5ビットの中で2か所に1を置くパターンは10通りある。
それぞれのビットで見れば、10通りのうちの2/5にあたる4通りでそこに1がある。
つまり、(16+8+4+2+1)*10*(2/5)=124が答えである。
では、与えられるnの値が、2の累乗2つの和より1小さい値の場合。
例えばn=19でk=2である場合。
まず、15以下の数の合計は、先ほどと同様の方法で(8+4+2+1)*6*(1/2)=45と求められる。
そして、16から19までの数は、3以下のpopcountが1である数に16を足したものが全てなので、
16*2+(2+1)*2*(1/2)=35と求められる。
これらを合わせて、19以下で条件を満たす数の総和は45+35=80とわかる。
例えばn=19でk=2である場合。
まず、15以下の数の合計は、先ほどと同様の方法で(8+4+2+1)*6*(1/2)=45と求められる。
そして、16から19までの数は、3以下のpopcountが1である数に16を足したものが全てなので、
16*2+(2+1)*2*(1/2)=35と求められる。
これらを合わせて、19以下で条件を満たす数の総和は45+35=80とわかる。
同じように、2の累乗いくつかの和より1小さい場合にもこれを繰り返せばよい。
そして、2の累乗いくつかの和より1小さい数というのは、どんな数でも該当する。
よって、どんな場合でもこれで解ける。
最初にnに1を加えてから、「n未満で条件を満たす～～」の方がコードが書きやすい。
そして、2の累乗いくつかの和より1小さい数というのは、どんな数でも該当する。
よって、どんな場合でもこれで解ける。
最初にnに1を加えてから、「n未満で条件を満たす～～」の方がコードが書きやすい。
答えはmod998244353での値なので、剰余類環も参照。
解答例
注意点
ビットシフトもlong long型で
うっかり1<<60とか書くと、ビットがint型からはみ出てただの0になる。
1LL<<60とすること。
1LL<<60とすること。
