ABC275-D Yet Another Recursive Function

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("0");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("100");
            //55
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long N = long.Parse(InputList[0]);
        Console.WriteLine(f(N));
    }

    static Dictionary<long, long> mMemo = new Dictionary<long, long>();
    static long f(long pN)
    {
        if (mMemo.ContainsKey(pN)) return mMemo[pN];

        if (pN == 0) return 1;
        return mMemo[pN] = f(pN / 2) + f(pN / 3);
    }
}

解説

log2(10^18)もlog3(10^18) も大きい数でないので
問題文通りに関数を定義して、メモ化再帰にしてます。