ABC150-E Change a Little Bit

問題へのリンク

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("1");
            WillReturn.Add("1000000000");
            //999999993
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("5 8");
            //124
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5");
            WillReturn.Add("52 67 72 25 79");
            //269312
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 1000000007;

    static void Main()
    {
        //ReSearch(6);

        List<string> InputList = GetInputList();
        long N = long.Parse(InputList[0]);
        long[] CArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        CArr = CArr.OrderByDescending(pX => pX).ToArray();

        // Nを引数として、加算回数の数列を返す
        List<long> SuuretuList = DeriveSuuretuList(N);

        long Answer = 0;
        for (int I = 0; I <= CArr.GetUpperBound(0); I++) {
            Answer += CArr[I] * SuuretuList[I];
            Answer %= Hou;
        }
        long Bekijyou = DeriveBekijyou(2, N, Hou);
        Answer *= Bekijyou;
        Answer %= Hou;
        Console.WriteLine(Answer);
    }

    // ビット数を引数として、ビットごとの加算で使う回数を調べる
    static void ReSearch(int pBitCnt)
    {
        int AllBitOn = (1 << pBitCnt) - 1;

        var CntDict = new Dictionary<int, int>();
        for (int I = 0; I <= AllBitOn; I++) {
            for (int J = 1; J <= pBitCnt; J++) {
                int CurrBitJ = (1 << (J - 1));
                if ((I & CurrBitJ) == 0) {
                    continue;
                }

                // 左にOnのビット数を数える
                for (int K = J; K <= pBitCnt; K++) {
                    int CurrBitK = (1 << (K - 1));
                    if ((I & CurrBitK) == 0) {
                        continue;
                    }
                    if (CntDict.ContainsKey(K) == false) {
                        CntDict[K] = 0;
                    }
                    CntDict[K]++;
                }
            }
        }

        foreach (var EachPair in CntDict) {
            Console.WriteLine("CntDict[{0}]={1}", EachPair.Key, EachPair.Value);
        }
    }

    static List<long> DeriveSuuretuList(long pN)
    {
        var WillReturn = new List<long>();
        long Syokou = DeriveBekijyou(2, pN, Hou);
        Syokou *= DeriveGyakugen(2);
        Syokou %= Hou;

        long Kousa = Syokou * DeriveGyakugen(2);
        Kousa %= Hou;

        WillReturn.Add(Syokou);
        while (WillReturn.Count < pN) {
            long CurrKou = WillReturn.Last();
            CurrKou += Kousa;
            CurrKou %= Hou;
            WillReturn.Add(CurrKou);
        }
        return WillReturn;
    }

    // 引数の逆元を求める
    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;
        }
    }
}

解説

N=5
コストの配列は
52 67 72 25 79
で考察すると

5ビットでの全ての数同士の順序対で
コストを集計する必要がありますが

ビット単位での差があるかのみが重要なので
00000と、全てのビットの組み合わせで集計し、
結果を32倍すれば良いと分かります。

ビットごとに、何度集計されるかは、
ReSearchメソッドで、等差数列になると分かるので
等差数列を求めて、集計してます。