Problem169 ある数を2のべき乗の和で表せる方法の数

問題

整数nを2のべき乗の和で表すことを考える. ただし各数は高々2回しか使ってはいけないものとする.
この表し方の数をf(n)とする. ただしf(0)=1と定義する.

例として n=10 を考える.

・1+1+8
・1+1+4+4
・1+1+2+2+4
・2+4+4
・2+8

と5通りの異なる表し方があるので, f(10)=5 である.
f(10の25乗)を求めよ.

ソース

using System;
using System.Collections.Generic;

class Program
{
    static int UB;

    static void Main()
    {
        Solve(10M);
        Solve(10000000000000000000000000M);
    }

    static void Solve(decimal pN)
    {
        string BinStr = DeriveBinStr(pN);
        UB = BinStr.Length - 1;

        //場合の数[現在の数値]なDP表
        var PrevDP = new Dictionary<string, long>();
        PrevDP.Add(BinStr.Replace('1', '0'), 1);

        for (int I = UB; 0 <= I; I--) {
            var CurrDP = new Dictionary<string, long>();
            foreach (var EachPair in PrevDP) {
                Action<string> MergeAct = (pNewKey) =>
                {
                    //枝切り処理
                    if (BinStr[I] != pNewKey[I]) return;

                    if (CurrDP.ContainsKey(pNewKey)) {
                        CurrDP[pNewKey] += EachPair.Value;
                    }
                    else CurrDP[pNewKey] = EachPair.Value;
                };

                //0回加算のケース
                string NewKey0 = EachPair.Key;
                MergeAct(NewKey0);

                //1回加算のケース
                bool IsOverFlow1;
                string NewKey1 = ExecKasan(EachPair.Key, I, out IsOverFlow1);
                if (IsOverFlow1 == false) MergeAct(NewKey1);

                //2回加算のケース
                if (I > 0) {
                    bool IsOverFlow2;
                    string NewKey2 = ExecKasan(EachPair.Key, I - 1, out IsOverFlow2);
                    if (IsOverFlow2 == false) MergeAct(NewKey2);
                }
            }
            Console.WriteLine("右から{0}桁目のDP結果", UB - I + 1);
            foreach (var EachPair in CurrDP) {
                Console.WriteLine("CurrDP[{0}]={1}", EachPair.Key, EachPair.Value);
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine("f({0})={1}", pN, PrevDP[BinStr]);
    }

    //2進数にしたString型を返す
    static string DeriveBinStr(decimal pN)
    {
        var ModList = new List<int>();
        decimal CopiedVal = pN;

        do {
            if (CopiedVal % 2 == 0) {
                ModList.Add(0);
                CopiedVal /= 2;
            }
            else {
                ModList.Add(1);
                CopiedVal = (CopiedVal - 1) / 2;
            }
        } while (CopiedVal > 0);

        ModList.Reverse();
        var sb = new System.Text.StringBuilder();
        ModList.ForEach(X => sb.Append(X));
        return sb.ToString();
    }

    //加算処理
    static string ExecKasan(string pStr, int pPos, out bool pIsOverFlow)
    {
        pIsOverFlow = false;

        char[] wkArr = pStr.ToCharArray();
        wkArr[pPos]++;

        //繰り上がりの処理
        for (int I = pPos; 0 <= I; I--) {
            if (wkArr[I] == '2') {
                if (I == 0) {
                    pIsOverFlow = true;
                    break;
                }
                wkArr[I] = '0';
                wkArr[I - 1]++;
            }
            else break;
        }
        return new string(wkArr);
    }
}

実行結果

省略
f(10000000000000000000000000)=178653872807

解説

2進数で小さい桁から、桁DPしてます。