halcの競プロ精進ブログ

はるくが競プロしたことを書き留めるなにか

【今日の精進】AISING2020F - Two Snuke

競プロ 今日の精進 企業コンテスト ABC 橙Diff

毎日格上の問題を倒すやつの44日目です。

問題リンク

atcoder.jp

問題概要

以下の条件をすべて満たす整数の組を考えるよ。

  • 0\leq s_1\leq s_2
  • 0\leq n_1\leq n_2
  • 0\leq u_1\leq u_2
  • 0\leq k_1\leq k_2
  • 0\leq e_1\leq 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_2-s_1)(n_2-n_1)(u_2-u_1)(k_2-k_1)(e_2-e_1) の総和を求めてね。

解法

以下の記事にFPSの基礎が詳しく載っています。

私もこれを参考に解いたので、最後の演習の私の答えを載せるにとどめておきます。

trap.jp

11.

手計算すれば (F_0,F_1,F_2,F_3,F_4,F_5,F_6,\dots)=(0,1,2,4,6,9,12,\dots) であることが容易にわかります。この時点で規則性を見つけておくと楽でしょう。

12.

先ほどの数列の階差を見てみると、(1,1,2,2,3,3,\dots) となります。慣れている人はこの時点で母関数を求められそうですが、少し難しいのでもう一回階差をとります。すると、(1,0,1,0,1,0,\dots) となります。

これは簡単な話で、漸化式 F_n=F_{n-2} と表せるため、母関数は \frac{1}{1-x^2} と表せます。

あとは2回階差をとったので2回累積和をとることで元の形に直します。 すると、F(x)=\frac{1}{(1-x^2)(1-x)^2} と表せます。

この場合 F_0=1 となってしまいますが、この後何か困ることはほとんどないので気にしないことにします。

13.

この関数を5乗すると、和がちょうど N の場合は解けます。

しかし、今回は「以下」を求めたいです。

これを1から愚直に求めると結局 O(N) かかってしまいます。

そのため、1-x で割って累積和を求めましょう。こうすると一か所を見るだけでよくなります。

答えは [x^{(N-5)}]\frac{1}{(1-x^2)^5(1-x)^{11}} となります*1。N-5 は先ほど F_0=1 とした弊害で、0次目が N=5 のときの解となっているためです。そのため-5しています。*2

14.

あとは展開して行列累乗なりBostan-moriで殴れば終わりです。

今回の母関数は約 40 次です。これを d として、

  • 行列累乗... O(d^3 \log N)
  • 愚直Bostan-mori... O(d^2 \log N)
  • 任意mod畳み込み+Bostan-mori... O(d\log d \log N)

となります。どれでも余裕をもって間に合いますが、提出コードは愚直Bostan-moriです。

提出コード

def bostan_mori(N,P,Q,MOD):
    while N>0:
        U=[0]*(len(P)+len(Q)-1)
        for i in range(len(P)):
            for j in range(len(Q)):
                if j%2==0:
                    U[i+j]+=P[i]*Q[j]
                else:
                    U[i+j]-=P[i]*Q[j]
                U[i+j]%=MOD
        P=U[N%2::2]
        V=[0]*(len(Q)*2-1)
        for i in range(len(Q)):
            for j in range(len(Q)):
                if j%2==0:
                    V[i+j]+=Q[i]*Q[j]
                else:
                    V[i+j]-=Q[i]*Q[j]
                V[i+j]%=MOD
        Q=V[0::2]
        N//=2
    return P[0]//Q[0]%MOD

T=int(input())
for _ in range(T):
    N=int(input())
    if N<5:
        print(0)
        continue
    print(bostan_mori(N-5,[1],[1, -11, 50, -110, 65, 253, -648, 440, 610, -1430, 780, 780, -1430, 610, 440, -648, 253, 65, -110, 50, -11, 1],10**9+7))

Submission #47166313 - AIsing Programming Contest 2020

感想

非人間的なDPもFPSで導出できるのおもしろすぎる…

*1:表し方あってるのかな

*2:題意は満たしてませんがちゃんと表せたのでよしということで…