ABC468-E Sum of Average

問題へのリンク

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("2");
            WillReturn.Add("2 3");
            //499122184
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6");
            WillReturn.Add("1 2 3 4 5 6");
            //499122250
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("9");
            WillReturn.Add("3 1 4 1 5 9 2 6 5");
            //855638200
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 998244353;

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] AArr = GetSplitArr(InputList[1]);
        long UB = AArr.GetUpperBound(0);

        var Ins_Fenwick_Tree = new Fenwick_Tree(UB, Hou);
        for (long I = 0; I <= UB; I++) {
            Ins_Fenwick_Tree[I] = AArr[I];
        }

        bool IsEven = (AArr.Length % 2 == 0);
        long LimitI = AArr.Length / 2;
        if (IsEven == false) {
            LimitI++;
        }

        long Answer = 0;
        long CurrSum = 0;

        long Head = 0;
        long Tail = UB;

        for (long I = 1; I <= LimitI; I++) {
            CurrSum += Ins_Fenwick_Tree.GetSum(Head, Tail);
            CurrSum %= Hou;

            Answer += CurrSum * DeriveGyakugen(I);
            Answer %= Hou;

            if (IsEven || I < LimitI) {
                long Pair = AArr.Length - I + 1;
                Answer += CurrSum * DeriveGyakugen(Pair);
                Answer %= Hou;
            }
            Head++;
            Tail--;
        }
        Console.WriteLine(Answer);
    }

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

// フェニック木
#region Fenwick_Tree
internal class Fenwick_Tree
{
    private long[] mBitArr;
    private long mExternalArrUB;
    private long mHou;

    // ノードのIndexの列挙を返す
    internal IEnumerable<long> GetNodeIndEnum()
    {
        for (long I = 0; I <= mExternalArrUB; I++) {
            yield return I;
        }
    }

    // 木のノードのUBを返す
    internal long GetUB()
    {
        return mExternalArrUB;
    }

    // コンストラクタ
    internal Fenwick_Tree(long pExternalArrUB, long pHou)
    {
        mExternalArrUB = pExternalArrUB;

        // フェニック木の外部配列は0オリジンで、
        // フェニック木の内部配列は1オリジンなため、2を足す
        mBitArr = new long[pExternalArrUB + 2];

        mHou = pHou;
    }

    // Indのチェック
    private void IndCheck(long pInd)
    {
        if (pInd < 0) throw new Exception("pInd < 0");
        if (mExternalArrUB < pInd) throw new Exception("UB < pInd");
    }

    // Indの大小チェック
    private void IndRangeCheck(long pSta, long pEnd)
    {
        IndCheck(pSta);
        IndCheck(pEnd);
        if (pSta > pEnd) throw new Exception("pSta > pEnd");
    }

    // インデクサ
    internal long this[long pInd]
    {
        get { return GetSum(pInd, pInd); }
        set { Add(pInd, value - GetSum(pInd, pInd)); }
    }

    // [pSta,pEnd] のSumを返す
    internal long GetSum(long pSta, long pEnd)
    {
        IndRangeCheck(pSta, pEnd);

        long Result = GetSum(pEnd);
        if (pSta > 0) {
            Result -= GetSum(pSta - 1);
        }

        Result %= mHou;
        if (Result < 0) Result += mHou;
        return Result;
    }

    // [0,pEnd] のSumを返す
    internal long GetSum(long pEnd)
    {
        IndCheck(pEnd);

        pEnd++; // 1オリジンに変更

        long Sum = 0;
        while (pEnd >= 1) {
            Sum += mBitArr[pEnd];
            Sum %= mHou;
            pEnd -= pEnd & -pEnd;
        }
        if (Sum < 0) Sum += mHou;
        return Sum;
    }

    // [I] に Xを加算
    internal void Add(long pI, long pX)
    {
        IndCheck(pI);

        pI++; // 1オリジンに変更

        pX %= mHou;
        while (pI <= mBitArr.GetUpperBound(0)) {
            mBitArr[pI] += pX;
            mBitArr[pI] %= mHou;
            pI += pI & -pI;
        }
    }
}
#endregion

解説

数列の値を
A B C D E
とし、分母ごとに寄与度を考えることにし、
縦軸を分母、値を加算回数とした表を作成します。

  A B C D E
1 1 1 1 1 1
2 1 2 2 2 1
3 1 2 3 2 1
4 1 2 2 2 1
5 1 1 1 1 1

数列の値を
A B C D
とし、分母ごとに寄与度を考えることにし、
縦軸を分母、値を加算回数とした表を作成します。

  A B C D
1 1 1 1 1
2 1 2 2 1
3 1 2 2 1
4 1 1 1 1

以上により、HeadとTailという変数を用意し、
HeadからTailまでの区間和を
CurrSumに計上しつつ、
要素数の偶奇で場合分けし、上下の対称分も
分母別で解に計上していき、解けると分かります。

また、1からNまでの逆元を順に求めてますが、
内部の、繰り返し2乗法は、O(lon(N))なので
TLEしないです。