Problem491 11で割り切れるダブルパンデジタル数

問題

0から9の数字をちょうど2回使った(先行ゼロのない)正整数をダブルパンデジタル数と呼ぼう.
例えば, 40561817703823564929 はそのような数の一つである.

11で割り切れるダブルパンデジタル数はいくつあるか?

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int KetaSuu = 20;
    const int Hou = 11;

    //4進数で管理するDPの状態
    //4の14乗=2の28乗なので、4進数ならオーバーフローしない
    struct JyoutaiDef
    {
        internal int ModVal; //11を法とした余り
        internal int[] AppearedCntArr; //0から9の登場数
    }

    static int GetHash(JyoutaiDef pJyoutai)
    {
        int WillReturn = 0;
        WillReturn += pJyoutai.ModVal;

        foreach (int EachInt in pJyoutai.AppearedCntArr) {
            WillReturn *= 4;
            WillReturn += EachInt;
        }
        return WillReturn;
    }

    static JyoutaiDef GetJyoutai(int pHash)
    {
        int CopiedHash = pHash;

        JyoutaiDef WillReturn;
        WillReturn.AppearedCntArr = new int[10];
        for (int I = 9; 0 <= I; I--) {
            WillReturn.AppearedCntArr[I] = CopiedHash % 4;
            CopiedHash /= 4;
        }
        WillReturn.ModVal = CopiedHash;
        return WillReturn;
    }

    static void Main()
    {
        //10進数での桁ごとの11を法とした余りを求めておく
        DeriveKetaModDict();

        //場合の数[状態のハッシュ値]なDP表
        var PrevDP = new Dictionary<int, long>();
        PrevDP.Add(0, 1);

        for (int I = 1; I <= KetaSuu; I++) {
            var CurrDP = new Dictionary<int, long>();

            foreach (var EachPair in PrevDP) {
                for (int J = 0; J <= 9; J++) {
                    //1桁目の0は不可
                    if (I == 1 && J == 0) continue;

                    JyoutaiDef CurrJyoutai = GetJyoutai(EachPair.Key);

                    CurrJyoutai.ModVal += mKetaModDict[I] * J;
                    CurrJyoutai.ModVal %= Hou;

                    if (CurrJyoutai.AppearedCntArr[J] == 2)
                        continue;
                    CurrJyoutai.AppearedCntArr[J]++;

                    int 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.ModVal > 0) continue;

            if (Array.TrueForAll(wkJyoutai.AppearedCntArr, X => X == 2))
                Answer += EachPair.Value;
        }
        Console.WriteLine("解は{0}通り", Answer);
    }

    //10進数での桁ごとの11を法とした余りを求めておく
    static Dictionary<int, int> mKetaModDict = new Dictionary<int, int>();
    static void DeriveKetaModDict()
    {
        int ModVal = 1;
        for (int I = KetaSuu; 1 <= I; I--) {
            mKetaModDict[I] = ModVal;

            ModVal *= 10;
            ModVal %= Hou;
        }
    }
}

実行結果

解は194505988824000通り

解説

BitDPで、桁DPしてます。