ABC178-C Ubiquity

問題へのリンク

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");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("869121");
            //2511445
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int N = int.Parse(InputList[0]);

        const long Hou = 1000000000 + 7;

        long Answer = DeriveModPow(10, N, Hou);
        Answer -= 2 * DeriveModPow(9, N, Hou);
        Answer %= Hou;
        if (Answer < 0) Answer += Hou;

        Answer += DeriveModPow(8, N, Hou);
        Answer %= Hou;

        Console.WriteLine(Answer);
    }

    //繰り返し2乗法で、(NのP乗) Mod Mを求める
    static long DeriveModPow(long pN, long pP, long pM)
    {
        long CurrJyousuu = pN % pM;
        long CurrShisuu = 1;
        long WillReturn = 1;

        while (true) {
            //対象ビットが立っている場合
            if ((pP & CurrShisuu) > 0) {
                WillReturn = (WillReturn * CurrJyousuu) % pM;
            }

            CurrShisuu *= 2;
            if (CurrShisuu > pP) return WillReturn;
            CurrJyousuu = (CurrJyousuu * CurrJyousuu) % pM;
        }
    }
}

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");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("869121");
            //2511445
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int N = int.Parse(InputList[0]);

        const long Hou = 1000000000 + 7;

        //場合の数[0と9の有無]なDP表
        var PrevDP = new Dictionary<int, long>();
        PrevDP[0] = 1;

        for (int I = 1; I <= N; I++) {
            var CurrDP = new Dictionary<int, long>();
            foreach (var EachPair in PrevDP) {
                for (int J = 1; J <= 3; J++) {
                    int NewKey = EachPair.Key;
                    int BaiSuu = 8; //0と9以外の数で8
                    if (J == 1) {
                        NewKey |= 1;
                        BaiSuu = 1;
                    }
                    if (J == 2) {
                        NewKey |= 2;
                        BaiSuu = 1;
                    }
                    if (CurrDP.ContainsKey(NewKey)) {
                        CurrDP[NewKey] += EachPair.Value * BaiSuu;
                        CurrDP[NewKey] %= Hou;
                    }
                    else {
                        CurrDP[NewKey] = EachPair.Value * BaiSuu;
                        CurrDP[NewKey] %= Hou;
                    }
                }
            }
            PrevDP = CurrDP;
        }
        if (PrevDP.ContainsKey(1 | 2)) {
            Console.WriteLine(PrevDP[1 | 2]);
        }
        else {
            Console.WriteLine(0);
        }
    }
}

解説

0が無い数列    9のN乗通り
9が無い数列    9のN乗通り
0も9も無い数列 8のN乗通り
全部の数列は  10のN乗通り

ベン図を書いて考えると、0と9を含む数列は、
10のN乗 - 2 * 9のN乗 + 8のN乗
となります。