Pinely Round 1 (Div. 1 + Div. 2) D. Carry Bit 別解

https://codeforces.com/contest/1761/problem/D

問題概要

非負整数 $x, y$ に対し $2$ 進数で $x+y$ を計算したときの繰り上がりの回数を $f(x, y)$ とおく。整数の組 $a, b \in [ 0, 2 ^ n)$ であって、 $f(a, b) = k$ であるようなものの個数を $10 ^ 9+7$ で割った余りを求めよ。

解法

$a _ {n,k}, b _ {n,k}$ を以下のように定義します。

整数 $a, b \in [ 0, 2 ^ n)$ であって、 $f(a, b) = k$ で $2^{n-1}$ の位から $2 ^ n$ の位への繰り上がりがあるものの個数を $a _ {n, k}$ とする。
整数 $a, b \in [ 0, 2 ^ n)$ であって、 $f(a, b) = k$ で $2^{n-1}$ の位から $2 ^ n$ の位への繰り上がりがないものの個数を $b _ {n, k}$ とする。

また、 $F(x,y) = \sum _ {n, k} a _ {n, k} x ^ n y ^ k, G(x,y) = \sum _ {n, k} b _ {n, k} x ^ n y ^ k$ とします。

このとき、 $F(x,y), G(x,y)$ について以下が成り立ちます。

$F(x,y) = 3xF(x,y) + xG(x,y) + 1$
$G(x,y) = xyF(x,y) + 3xyG(x,y)$

$(1-3xy)G(x,y)=xyF(x,y)$ なので、上の式の両辺を $(1-3xy)$ 倍しこれを代入すると

$(1-3xy)F(x,y) = 3x(1-3xy)F(x,y) + x ^ 2yF(x,y) + (1-3xy)$

$F(x,y) = \frac{1-3xy}{1-3x-3xy+8x ^ 2y}$

よって $G(x,y) = \frac{xy}{1-3x-3xy+8x ^ 2y}$ なので、

$F(x,y)+G(x,y) = \frac{1-2xy}{1-3x-3xy+8x ^ 2y} = (1-2xy) \sum _ {i=0} ^ {\infty} (3x+3xy-8x ^ 2y) ^ i$ となります。

求めたい答えは $[ x ^ ny ^ k ] (F(x,y)+G(x,y)) = [ x ^ n y ^ k ] (1-2xy) \sum _ {i = 0} ^ {\infty} (3x+3xy-8x ^ 2y) ^ i$ なので、 $n, k$ について $[ x ^ n y ^ k ] \sum _ {i = 0} ^ {\infty} (3x+3xy-8x ^ 2y) ^ i$ を求めることを考えます。

多項定理を用いて展開して

$[ x ^ n y ^ k ] \sum _ {i = 0} ^ {\infty} (3x+3xy-8x ^ 2y) ^ i = [ x ^ n y ^ k ] \sum _ {a,b,c} \frac{(a+b+c)!}{a!b!c!} (3x) ^ a (3xy) ^ b (-8x ^ 2y) ^ c$ となります。

次数を比較すると、 $a+b+2c=n, b+c=k$ となるような $a, b, c$ のみ考えればよいです。 $c$ を固定すると $a, b$ は一意に定まります。この $a, b, c$ について $\frac{(a+b+c)!}{a!b!c!} 3 ^ {a+b} (-8) ^ c$ を計算し、総和を求めればよいです。

実装

https://codeforces.com/contest/1761/submission/186767977