ABC224-F Problem where +s Separate Digits

問題へのリンク

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

    const long Hou = 998244353;

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[0];
        long UB = S.Length - 1;

        long Answer = 0;
        for (long I = 0; I <= UB; I++) {
            long CurrSum = 0;

            // 後続の+を入れる候補マスの数
            long RightSpaceCnt = UB - I;

            long CurrNum = S[(int)I] - '0';

            if (RightSpaceCnt == 0) {
                CurrSum += CurrNum;
                CurrSum %= Hou;
            }
            else {
                // 等比数列の初項
                long Syokou = CurrNum * DeriveBekijyou(2, RightSpaceCnt - 1, Hou);
                Syokou %= Hou;

                long Kousuu = RightSpaceCnt;
                CurrSum += DeriveTouhisuuretuSum(Syokou, 10 / 2, Kousuu, Hou);
                CurrSum %= Hou;

                CurrSum += CurrNum * DeriveBekijyou(10, RightSpaceCnt, Hou);
                CurrSum %= Hou;
            }

            long LeftSpaceCnt = I;
            CurrSum *= DeriveBekijyou(2, LeftSpaceCnt, Hou);
            CurrSum %= Hou;

            Answer += CurrSum;
            Answer %= Hou;
        }
        Console.WriteLine(Answer);
    }

    // 初項,公比,項数,法を引数とし、等比数列の和を返す(法が逆元を持つ場合)
    static long DeriveTouhisuuretuSum(long pSyokou, long pR, long pKousuu, long pHou)
    {
        // 公比が1の場合
        if (pR == 1) {
            return (pSyokou * pKousuu) % pHou;
        }

        long Result = pSyokou * (DeriveBekijyou(pR, pKousuu, pHou) - 1);
        Result %= pHou;
        Result *= DeriveGyakugen(pR - 1);
        Result %= pHou;
        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;
        }
    }
}

解説

56789というサンプルで考察し
プラスを入れる候補に□を記述します

5□6□7□8□9

5は
    5*(2の3乗)
   50*(2の2乗)
  500*(2の1乗)
 5000*1
50000*1
で合計に計上されます。
5*(2の3乗)を初項として、公比 10/2 の 等比数列があるので、
等比数列の和の公式が使えます。

同様に
6は
    6*(2の2乗)
   60*(2の1乗)
  600*1
 6000*1
で合計に計上されます。
6の左の□は自由に決めれるので、計上する合計も2倍になります。

同様に
7は
    7*(2の1乗)
   70*1
  700*1
で合計に計上されます。
7の左の2つの□は自由に決めれるので、計上する合計も4倍になります。

以上のようにして、解を求めることができます。