エイシング プログラミング コンテスト 2020 D Anything Goes to Zero

問題へのリンク

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

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

        long BasePopCnt = StrX.ToCharArray().Count(pX => pX == '1');

        // 法を引数として、合計値を返す
        Func<long, long> DeriveSum = (pHou) =>
        {
            long SumVal = 0;
            long BekiVal = 1;
            for (int I = UB; 0 <= I; I--) {
                if (StrX[I] == '1') {
                    SumVal += BekiVal;
                    SumVal %= pHou;
                }
                BekiVal *= 2;
                BekiVal %= pHou;
            }
            return SumVal;
        };

        long SumPlus = DeriveSum(BasePopCnt + 1);
        long SumMinus = 0;
        if (BasePopCnt - 1 > 0) {
            SumMinus = DeriveSum(BasePopCnt - 1);
        }

        for (int I = 0; I <= UB; I++) {
            long CurrMod;
            long CurrSum;
            if (StrX[I] == '0') {
                CurrMod = BasePopCnt + 1;
                CurrSum = SumPlus;
            }
            else {
                CurrMod = BasePopCnt - 1;
                CurrSum = SumMinus;
            }

            if (CurrMod == 0) {
                Console.WriteLine(0);
                continue;
            }

            long CurrVal = DeriveBekijyou(2, UB - I, CurrMod);

            if (StrX[I] == '0') {
                CurrSum += CurrVal;
            }
            else {
                CurrSum -= CurrVal;
            }

            CurrSum %= CurrMod;
            if (CurrSum < 0) CurrSum += CurrMod;

            Console.WriteLine(1 + DeriveCnt(CurrSum));
        }
    }

    // 繰り返し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;
        }
    }

    // 引数の値の、0までの変換回数を求める
    static long DeriveCnt(long pVal)
    {
        if (pVal == 0) return 0;
        long ModVal = PopCount(pVal);
        return 1 + DeriveCnt(pVal % ModVal);
    }

    ////////////////////////////////////////////////////////////////
    // C++のPopCount
    ////////////////////////////////////////////////////////////////
    static long PopCount(long pVal)
    {
        long WillReturn = 0;
        while (pVal > 0) {
            if (pVal % 2 == 1) WillReturn++;
            pVal /= 2;
        }
        return WillReturn;
    }
}

解説

PopCountは、桁に重みのない2進数だと考えて、
PopCountでModを取ると考えると、
1回の操作で、2進数での桁数以下になると分かります。

後は、
最初の1回目の操作だけは、
事前に2つの法での和との差分から求めるようにして、
2回目以降の操作は、ナイーブに求めることができます。