ABC158-E Divisible Substring

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("4 3");
            WillReturn.Add("3543");
            //6
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 2");
            WillReturn.Add("2020");
            //10
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("20 11");
            WillReturn.Add("33883322005544116655");
            //68
        }
        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(pX => long.Parse(pX)).ToArray();
        long P = wkArr[1];
        string S = InputList[1];
        long UB = S.Length - 1;

        Action<string> RegexAct = (pPattern) =>
        {
            MatchCollection Matches = Regex.Matches(S, pPattern);
            long SumLen = 0;
            foreach (Match EachMath in Matches) {
                SumLen += EachMath.Index + 1;
            }
            Console.WriteLine(SumLen);
        };

        if (P == 2) {
            RegexAct("[02468]");
            return;
        }
        if (P == 5) {
            RegexAct("[05]");
            return;
        }

        long Base = 1;
        var ModList = new List<long>();
        for (long I = UB; 0 <= I; I--) {
            long CurrVal = S[(int)I] - '0';
            CurrVal *= Base;
            ModList.Add(CurrVal % P);
            Base *= 10;
            Base %= P;
        }

        long[] RunSumArr = ModList.ToArray();
        for (long I = 1; I <= RunSumArr.GetUpperBound(0); I++) {
            RunSumArr[I] += RunSumArr[I - 1];
            RunSumArr[I] %= P;
        }

        long Answer = 0;
        foreach (var EachItem in RunSumArr.GroupBy(pX => pX)) {
            if (EachItem.Key == 0) {
                Answer += EachItem.LongCount(); // 0は単独で選択可能
            }
            Answer += EachItem.LongCount() * (EachItem.LongCount() - 1) / 2;
        }
        Console.WriteLine(Answer);
    }
}

解説

31415926535
という文字列で
右からの累積和のModを求めてから、
159の区間和を考えると

159の区間和をX
26535の区間和をA
15926535の区間和をB
とおいて、
X = (A-B) / 100000
X * 100000 = A - B

XがPの倍数かに興味があるので
Xを10を掛けたものであっても、Pと10が互いに素であれば
倍数判定には、影響がないです。

なので、累積和が一致するペアの個数は解になります。

10と互いに素でない、2と5は、場合分けしておいてから
正規表現で数えてます。