かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

AtCoder エイシング プログラミング コンテスト 2020 F - Two Snuke

問題はこちら

問題概要

  • {0\leq s_1 < s_2}
  • {0\leq n_1 < n_2}
  • {0\leq u_1 < u_2}
  • {0\leq k_1 < k_2}
  • {0\leq e_1 < e_2}
  • {s_1+s_2+n_1+n_2+u_1+u_2+k_1+k_2+e_1+e_2\leq N}

を満たす整数{s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2}の組全てについて
{(s_2-s_1)(n_2-n_1)(u_2-u_1)(k_2-k_1)(e_2-e_1)}の総和を求めよ.

{1\leq N \leq 10^9}

解説


形式的冪級数で解きます.{k=s_1+s_2}とすると{1\leq s_2-s_1=k-2s_1}
よって{\displaystyle 0\leq s_1\leq \frac{k-1}{2}}

{\displaystyle f=\sum_{k=0}^{\infty}\sum_{s_1=0}^{\left\lfloor\frac{k-1}{2}\right\rfloor}(k-2s_1)x^k}として{\displaystyle[x^N]\frac{f^5}{1-x}}が答え.

{k}を偶奇{k=2i, k=2i+1}で分けると
{\displaystyle\sum_{k=0}^{\infty}\sum_{s_1=0}^{\left\lfloor\frac{k-1}{2}\right\rfloor}(k-2s_1)x^k\\
\displaystyle =\sum_{i=0}^{\infty}\sum_{s_1=0}^{i-1}(2i-2s_1)x^{2i}+\sum_{i=0}^{\infty}\sum_{s_1=0}^{i}(2i+1-2s_1)x^{2i+1}\\
\displaystyle =\sum_{i=0}^{\infty}i(i+1)x^{2i}+\sum_{i=0}^{\infty}(i+1)^2x^{2i+1}\\
\displaystyle =\frac{2x^2}{(1-x^2)^3}+\frac{x(1+x^2)}{(1-x^2)^3}\\
\displaystyle = \frac{x}{(1-x)^3(1+x)}}

したがって{\displaystyle[x^{N-5}]\frac{1}{(1-x)^{16}(1+x)^5}}

Bostan–Moriのアルゴリズムを用いたり,線形漸化式に直して行列累乗したりすると{O(\log{N})}

ライブラリとか除くと実装はこれだけ

int main() {
    int t;cin >> t;
    while(t--) {
        ll n;cin >> n;
        FormalPowerSeries<MOD,true> f({1});
        for (int i = 0; i < 16; i++) f *= {1,-1};
        for (int i = 0; i < 5; i++) f *= {1,1};
        cout << Bostan_Mori({1},f,n-5) << endl;
    }
    return 0;
}

提出プログラム

https://atcoder.jp/contests/aising2020/submissions/21850352

感想

形式的冪級数おそるべし.