典型90問 082 Counting Numbers（★3）

問題へのリンク

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("3 5");
            //12
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("98 100");
            //694
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1001 869120");
            //59367733
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("381453331666495446 746254773042091083");
            //584127830
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 1000000007;

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

        //DeriveNumSum(1000000000000000000);
        //return;

        long Answer = DeriveNumSum(R);
        if (1 < L) {
            Answer -= DeriveNumSum(L - 1);
            if (Answer < 0) Answer += Hou;
        }
        Answer %= Hou;
        Console.WriteLine(Answer);
    }

    // 1からRまでの数字の数の合計を返す
    static long DeriveNumSum(long pR)
    {
        long NumSum = 0;

        long RangeSta = 1;
        long RangeEnd = 9;
        long Keta = 1;
        while (RangeSta <= pR) {
            long Syokou = Keta * (RangeSta % Hou);
            long Kousa = Keta;

            // 真に大きい場合
            if (RangeEnd < pR) {
                long Kousuu = RangeEnd - RangeSta + 1;
                NumSum += DeriveTousaSuuretuSum(Syokou, Kousa, Kousuu, Hou);
                NumSum %= Hou;
            }
            else {
                long Kousuu = pR - RangeSta + 1;
                NumSum += DeriveTousaSuuretuSum(Syokou, Kousa, Kousuu, Hou);
                NumSum %= Hou;
            }

            // オーバフロー対策でDecimal型でチェックする
            decimal DecRangeSta = (decimal)RangeSta * 10;
            if (DecRangeSta > pR) break;
            RangeSta *= 10;

            decimal DecRangeEnd = (decimal)RangeEnd * 10 + 9;
            if (DecRangeEnd > pR) {
                RangeEnd = pR;
            }
            else {
                RangeEnd = RangeEnd * 10 + 9;
            }

            Keta++;
        }
        return NumSum;
    }

    // 初項と公差と項数と法を引数として、等差数列の和を返す
    static long DeriveTousaSuuretuSum(long pSyokou, long pKousa, long pKouCnt, long pHou)
    {
        pSyokou %= Hou;
        pKousa %= Hou;
        pKouCnt %= Hou;
        long Makkou = pSyokou + pKousa * (pKouCnt - 1);
        Makkou %= Hou;
        long wkSum = (pSyokou + Makkou) % Hou;
        wkSum %= Hou;
        long Result = wkSum * pKouCnt;
        Result %= Hou;
        Result *= DeriveGyakugen(2);
        Result %= Hou;
        return Result;
    }

    // 引数の逆元を求める
    static long DeriveGyakugen(long pLong)
    {
        return DeriveBekijyou(pLong, Hou - 2, Hou);
    }

    // 繰り返し2乗法で、(NのP乗) Mod Mを求める
    static long DeriveBekijyou(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;
        }
    }
}

解説

[L,R]を
[1,L-1]と[1,R]
の2つの区間で分けて考えてます。

桁ごとに等差数列に分解して、
等差数列の和の公式を使ってます。