ARC122-A Many Formulae

問題へのリンク

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("3 1 5");
            //15
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("1 1 1 1");
            //10
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add("866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117");
            //279919144
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 1000000007;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        Solve(AArr);
    }

    // 0,1,1,2,3,5,8という並びのフィボナッチ数列
    static long[] FibonacciArr;

    // マイナスのノードからマイナスのノードへの辺が無いグラフとみなして解く
    // ノードごとに、開始ノードからの経路数と
    // そのノードから右端までの経路数を求めれば、
    // 場合の数の積の法則で、そのノードを経由する経路数が分かる
    static void Solve(long[] pAArr)
    {
        // フィボナッチ数列を求める
        FibonacciArr = new long[pAArr.Length + 2];
        for (long I = 0; I <= FibonacciArr.GetUpperBound(0); I++) {
            if (I == 0) FibonacciArr[I] = 0;
            else if (I == 1) FibonacciArr[I] = 1;
            else if (I == 2) FibonacciArr[I] = 1;
            else {
                FibonacciArr[I] = FibonacciArr[I - 1] + FibonacciArr[I - 2];
                FibonacciArr[I] %= Hou;
            }
        }

        long UB = pAArr.GetUpperBound(0);

        long[,] mFromPatternCntArr = new long[UB + 1, 2];
        long[,] mToPatternCntArr = new long[UB + 1, 2];

        for (long I = 0; I <= UB; I++) {
            mFromPatternCntArr[I, 0] = FibonacciArr[I + 1];
            mFromPatternCntArr[I, 1] = FibonacciArr[I];
        }

        for (long I = UB; 0 <= I; I--) {
            long RevInd = UB - I;
            mToPatternCntArr[I, 0] = FibonacciArr[RevInd + 2];
            mToPatternCntArr[I, 1] = FibonacciArr[RevInd + 1];
        }

        long Answer = 0;
        for (long I = 0; I <= UB; I++) {
            Answer += ((pAArr[I] * mFromPatternCntArr[I, 0]) % Hou) * mToPatternCntArr[I, 0];
            Answer %= Hou;
            Answer += ((-pAArr[I] * mFromPatternCntArr[I, 1]) % Hou) * mToPatternCntArr[I, 1];
            Answer %= Hou;
        }
        if (Answer < 0) Answer += Hou;
        Console.WriteLine(Answer);
    }
}

解説

1 2 3 4 5 という数列で考えると

   2  3  4  5
1
  -2 -3 -4 -5

という無向グラフで
-2から-3や-3から-4などには辺が無し
1からは、2と-2に辺が有り
2からは、3と-3に辺が有り
-2からは、3のみに辺が有り
といった辺があると考えて、

ノードごとに、開始ノードからの経路数と
そのノードから右端のノードへの経路数を
求めて、積の法則で求めた場合の数 * そのノード値を
全てのノードについて行って総和を求めれば、解になります。

各ノードへの経路数は、正順と逆順で考察すれば
フィボナッチ数列だと分かります。