AtCoder エイシング プログラミング コンテスト 2020 F - Two Snuke
問題概要
問題ページはこちら．
与えられる整数 $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)$ の総和 を $\mod 10^9+7$ で求めよ．$T$個のテストケースが与えられる．
- $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$
制約: $T \leq 100$, $N \leq 10^9$．
コンテストでは
そもそも，この問題の前のE問題を解き終わったのが終了5分前だったので，どうにもなりませんが，終了後しばらく考えてもまったく歯が立ちませんでした． 以下の解法は，editorial ほぼそのままです (だと思います)．
形式的冪級数も勉強しなくては....
解法
$s = 2s_1$, $\Delta s = s_1 - s_2$, $n = 2n_1$, $\Delta n = n_1 - n_2$ などとすると，与えられた条件は以下のように書き直される．
- $s\geq 0$, $s$は偶数．
- ...(n, u, k, e について略)...
- $\Delta s \geq 1$
- ...(n, u, k, e について略)...
- $s + n + u + k + e + \Delta s + \Delta n + \Delta u + \Delta k + \Delta e \leq N$
数えたいものは，$\Delta s \Delta n \Delta u \Delta k \Delta e$． これは，次の場合の数に一致する．
- $N$個のボールに10個の仕切りを入れ，できる11個のボールグループが次の2条件を満たすようにした上で，
- グループ1からグループ5は偶数になる
- グループ6からグループ10は1個以上になる
- グループ6からグループ10のそれぞれから，ボールを1個ずつ選ぶ
さらに，ボールを選ぶ代わりに仕切りを入れるようにすれば，次の場合の数であると言い直すことができる．
- $N-5$個のボールに15個の仕切りを入れ，グループ1からグループ5が偶数になるようにする
これを動的計画法で求める．dp[i,j,p] ($0\leq i \leq N+10$, $0\leq j \leq 15$, $0\leq p \leq 1$) を，次の場合の数とする．
- ボールと仕切りの数が合わせて i 個．
- 仕切りの数が j 個．
- p = 0 のとき，最後のボールグループの数が偶数．p = 1 のとき，最後のボールグループの数が奇数．
すると，以下のように遷移が考えられる．
- dp[i, j, p] で数えられている並びにボールが来ると，dp[i+1, j, 1-p] で数えられる並びとなる．
- dp[i, j, p] で数えられている並びに仕切りが来ると，dp[i+1, j+1, 0] で数えられる並びとなる．ただし，$j \leq 4$の時には，$p = 0$ でなければならない．
これを愚直に計算すると，$N$回のループを回す必要があるので，間に合わない．上の遷移は線形であることを利用する．具体的には，列ベクトル v[i] を $[\textrm{dp}(i, 0, 0), \textrm{dp}(i, 0, 1), \textrm{dp}(i, 1, 0), \textrm{dp}(i, 1, 1), \ldots, \textrm{dp}(i, 15, 1)]^T$ で定義すると，32次正方行列 $A$ を用いて，$v[i+1] = Av[i]$ と書ける．具体的には，$A$ の$i,j$成分を$A(i,j)$と書くと，上の遷移に対応して，
- $ A(2j + 1-p, 2j + p) = 1$
- $j \geq 5$ または $p = 0$ のとき，$A(2(j+1) + 0, 2j + p) = 1$
であり，それ以外の $A(i, j)$ は $0$ である．$v[N+10]$の最後の2成分の和が求める答であり，$v[N+10] = A^{N+10}v[0]$ であるから，$A$の冪乗を高速に求めれば良い．
実装
ライブラリのサイズが大きいですが，main関数だけ見ていただければ．$j \geq 5$ では，パリティを見る必要はないので，各jに対して1成分だけ使うようにしています．
