【今日の精進】ABC050/ARC066D - Xor Sum

毎日格上の問題を倒すやつの70日目です。

問題リンク

atcoder.jp

問題概要

以下の整数の組 であって、 を満たす が存在するようなものの個数を で割ったあまりを求めてね。

解法

愚直を書いてOEISにぶちこむと、1,2,4,5,8,10,13,14,18,21,26,28 - OEISが見つかります。

これにばっちり漸化式も記されているので、それを実装して終わりです。

提出コード

MOD=10**9+7
def calc(N):
    global used
    if N in used:
        return used[N]
    if N==0:
        return 0
    if N==1:
        return 1
    if N%2==0:
        used[N]=(calc(N//2)*2+calc(N//2-1))%MOD
    else:
        used[N]=(calc(N//2)*2+calc(N//2+1))%MOD
    return used[N]

used={}
print(calc(int(input())+1))

Submission #48020926 - AtCoder Beginner Contest 050

感想

真面目に、解きなさい…