Cは一見難しそうに見えるが、テストケースをもとに-2進数について考えれば解ける問題だった。Dについても、しっかりテストケースについて考えれば法則性が見えるので自力で解けた。
https://atcoder.jp/contests/abc105
C問題
数字Nについて-2進数で表すという問題であるが、まず簡単な例として2進数を考えてみる。ある数M(10進数)を2進数に変えるには、Mを2割っていきあまりを記録していき、最後に記録したあまりを逆順に表示すれば良い。同様に-2進数についても同様にある数Nについて-2で割っていき、あまりを記録することで、最後にそれを逆順に表示すれば答えになる。ここで、一つ注意しなければならないのがNを-2で割る際に、Nが負の数だったら、N/-2商は+1しなければならない。
D問題
M人の子供に、l~RまでのAについてのお菓子の和を均等に配るには、l~Rまでのお菓子の和がMの倍数でなければならない。まず、明らかに累積和をとる方が早いので、累積和をとる。その後、Mの倍数であることを確認するため、累積和のmodMをとる。ここで、0になったところは条件を満たすので答えにカウントする。ここで、累積和についてmodMをとった配列をSと呼ぶと、答えにカウントする条件はSについて、l,rを考えた時、Sl-1,Srが等しいことを意味する。よってSについてそれぞれ出現する数を記録していき、出現回数がk回(k>=2)のものについて、k = 1になるまでforで回し、kを答えにカウントしていけば良い。