yukicoder No.978 Fibonacci Convolution Easy(★2.5)
問題:No.978 Fibonacci Convolution Easy - yukicoder
解答:#479634 (C++14) No.978 Fibonacci Convolution Easy - yukicoder
解法:下記の足し算。
a1 * a1
a2 * a1 + a2 * a2
a3 * a1 + a3 * a2 + a3 * a3
これはsm = a1 + a2 + a3 + ... + an, diag = a1 * a1 + a2 * a2 + ... + an * anを用いてdiag + (sm * sm - diag) / 2 と表せる。