TopCoder SRM 723 Div2 Hard: SimpleMazeEasy

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

$N \times N$ の部屋が十字型に並んでいる。 (詳細は原文をご覧ください)

すべての部屋と部屋の間の最短距離の総和を求めよ。

解説

※ちゃんとした解説は kmjp さんのブログにあります。

変数が $1$ つしかないので、愚直解で最初の方を求めて OEIS したい気分になります。

というわけで愚直解を書くと、 $16, 600, 4680, 19904, 61000, 152136 \dots$ になることが分かるため、それを投げます。

しかしこの数列は OEIS にはありません (悲しいね)

ところでこの場合の数はどんなオーダーで増えていくでしょうか？

まず、点は $O(N^{2})$ 個あります。その点とペアになりうる点もまた $O(N^{2})$ 個あります。そして、ペアとの距離は $O(N)$ です。ということで、 $O(N^{5})$ 程度の多項式になりそうである予想が (プロは) 思いつきます (自分は思い付きませんでした)

この過程と先ほどの愚直解から、 $f(x) = c_{5} x^{5} + c_{4} x^{4} + c_{3} x^{3} + c_{2} x^{2} + c_{1} x + c_{0}$ を †ニュートン補間† や †ラグランジュ補間† などで気合で求めると $O(1)$ で解くことができます。

ソースコード

long long mod_pow(long long N, long long K) {
    long long t = N % MOD, ret = 1;
    while(K) {
        if(K & 1) (ret *= t) %= MOD;
        (t *= t) %= MOD;
        K >>= 1;
    }
    return ret;
}

class SimpleMazeEasy {
    public:
    int findSum(long long n) {
        long long vl = (333333332LL * mod_pow(n, 3)) % MOD;
        long long vr = (666666691LL * mod_pow(n, 5)) % MOD;
        return (int)((vl + vr) % MOD);
    }
};