TDP D サイコロ

■■■問題■■■

サイコロをN回振ったとき、出た目の積がDの倍数となる確率を求めよ

■■■制約■■■

1 <= N <= 100
1 <= D <= 10の18乗

■■■入力■■■

N D

■■■出力■■■

答えを1行に出力せよ。
絶対誤差が 10の-6乗以下のとき正当と判定される。

C#のソース

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

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("2 6");
            //0.416666667
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 2");
            //0.875
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(X => long.Parse(X)).ToArray();
        long N = wkArr[0];
        long D = wkArr[1];

        int Jyousuu2, Jyousuu3, Jyousuu5;
        bool Exist7IjyouSoinsuu;
        ExecSoinsuuBunkai(D, out Jyousuu2, out Jyousuu3, out Jyousuu5,
                          out Exist7IjyouSoinsuu);

        // 7以上の素因数がある場合
        if (Exist7IjyouSoinsuu) {
            Console.WriteLine("0");
            return;
        }

        // 遷移確率[2の乗数,3の乗数,5の乗数]なDP表
        double[, ,] CurrDP = new double[Jyousuu2 + 1, Jyousuu3 + 1, Jyousuu5 + 1];
        double[, ,] PrevDP = new double[Jyousuu2 + 1, Jyousuu3 + 1, Jyousuu5 + 1];
        PrevDP[0, 0, 0] = 1; // 初期設定

        int UB_2 = PrevDP.GetUpperBound(0);
        int UB_3 = PrevDP.GetUpperBound(1);
        int UB_5 = PrevDP.GetUpperBound(2);

        for (int LoopN = 1; LoopN <= N; LoopN++) {
            Array.Clear(CurrDP, 0, CurrDP.Length);
            for (int Dice = 1; Dice <= 6; Dice++) {
                for (int Loop2 = 0; Loop2 <= UB_2; Loop2++) {
                    for (int Loop3 = 0; Loop3 <= UB_3; Loop3++) {
                        for (int Loop5 = 0; Loop5 <= UB_5; Loop5++) {
                            if (PrevDP[Loop2, Loop3, Loop5] == 0) break;
                            int NewInd2 = Loop2;
                            int NewInd3 = Loop3;
                            int NewInd5 = Loop5;

                            if (Dice == 2 || Dice == 6) NewInd2++;
                            if (Dice == 3 || Dice == 6) NewInd3++;
                            if (Dice == 4) NewInd2 += 2;
                            if (Dice == 5) NewInd5++;

                            // UB超えなら、UBに戻す
                            if (NewInd2 > UB_2) NewInd2 = UB_2;
                            if (NewInd3 > UB_3) NewInd3 = UB_3;
                            if (NewInd5 > UB_5) NewInd5 = UB_5;

                            // 確率の乗法定理でDP表を更新
                            CurrDP[NewInd2, NewInd3, NewInd5]
                                += PrevDP[Loop2, Loop3, Loop5] / 6;
                        }
                    }
                }
            }
            Array.Copy(CurrDP, PrevDP, CurrDP.Length);
        }
        Console.WriteLine(PrevDP[UB_2, UB_3, UB_5]);
    }

    // 素因数分解して、
    // 2の乗数、3の乗数、5の乗数
    // 7以上の素因数がないかを返す
    static void ExecSoinsuuBunkai(long pD,
                                  out int pJyousuu2,
                                  out int pJyousuu3,
                                  out int pJyousuu5,
                                  out bool pExist7IjyouSoinsuu)
    {
        pJyousuu2 = pJyousuu3 = pJyousuu5 = 0;
        while (pD % 2 == 0) { pD /= 2; pJyousuu2++; }
        while (pD % 3 == 0) { pD /= 3; pJyousuu3++; }
        while (pD % 5 == 0) { pD /= 5; pJyousuu5++; }
        pExist7IjyouSoinsuu = (pD > 1);
    }
}

解説

サイコロの目の中で素数の数は、2と3と5ですので
最初に、Dを素因数分解して、7以上の素因数があったら、0が解となります。

次に、動的計画法で、
サイコロを1回振るごとの、サイコロの目の総積での、2の乗数、3の乗数、5の乗数、それぞれの値を
確率の乗法定理を使って、順に求めてます。