Problem162 16進数

問題

16進法では, 数は以下の16個の数字によって表される
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
16進数の AF は, 10進法での 10*16 + 15 = 175 と等しい.

3桁の16進数 10A, 1A0, A10, A01 には, 0, 1, A の全てが現れている.
10進数で書くときと同様に, 先頭の0は書かないことにする.

0, 1, A がそれぞれ少なくとも1回は現れるような16桁までの16進数はいくつ存在するか?
16進数で答えよ.

(A,B,C,D,E,F は大文字とし, 先頭や末尾の16進数であることを表す記号や先頭の0は許されない.
つまり, 1A3F ならOK. 1a3f, 0x1a3f, $1A3F, #1A3F, 0000001A3Fは許されない. )

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int KetaSuu = 16;

    struct JyoutaiDef
    {
        internal bool Has0;
        internal bool Has1;
        internal bool HasA;
        internal bool IsAppearNonZero;
    }

    static string GetHash(JyoutaiDef pJyoutai)
    {
        var sb = new System.Text.StringBuilder();
        sb.Append(pJyoutai.Has0 ? '1' : '0');
        sb.Append(pJyoutai.Has1 ? '1' : '0');
        sb.Append(pJyoutai.HasA ? '1' : '0');
        sb.Append(pJyoutai.IsAppearNonZero ? '1' : '0');
        return sb.ToString();
    }

    static JyoutaiDef GetJyoutai(string pHash)
    {
        JyoutaiDef WillReturn;
        WillReturn.Has0 = pHash[0] == '1';
        WillReturn.Has1 = pHash[1] == '1';
        WillReturn.HasA = pHash[2] == '1';
        WillReturn.IsAppearNonZero = pHash[3] == '1';
        return WillReturn;
    }

    static void Main()
    {
        //場合の数[状態のハッシュ値]なDP表
        var PrevDP = new Dictionary<string, long>();
        PrevDP.Add("0000", 1);

        for (int I = 1; I <= KetaSuu; I++) {
            var CurrDP = new Dictionary<string, long>();
            foreach (var EachPair in PrevDP) {
                for (int J = 0; J <= 15; J++) {
                    JyoutaiDef CurrJyoutai = GetJyoutai(EachPair.Key);
                    if (CurrJyoutai.IsAppearNonZero && J == 0)
                        CurrJyoutai.Has0 = true;

                    if (J == 1) CurrJyoutai.Has1 = true;
                    if (J == 10) CurrJyoutai.HasA = true;

                    if (J != 0) CurrJyoutai.IsAppearNonZero = true;

                    string NewKey = GetHash(CurrJyoutai);
                    if (CurrDP.ContainsKey(NewKey))
                        CurrDP[NewKey] += EachPair.Value;
                    else CurrDP[NewKey] = EachPair.Value;
                }
            }
            PrevDP = CurrDP;
        }

        long Answer = 0;
        foreach (var EachPair in PrevDP) {
            JyoutaiDef wkJyoutai = GetJyoutai(EachPair.Key);
            if (wkJyoutai.Has0 == false) continue;
            if (wkJyoutai.Has1 == false) continue;
            if (wkJyoutai.HasA == false) continue;
            Answer += EachPair.Value;
        }

        Console.WriteLine("10進数だと、{0}個", Answer);
        Console.WriteLine("16進数だと、{0}個", Answer.ToString("X"));
    }
}

実行結果

10進数だと、4420408745587516162個
16進数だと、3D58725572C62302個

解説

桁DPで解いてます。