はまやんはまやんはまやん

hamayanhamayan's blog

recurrence formula [yukicoder No.554]

https://yukicoder.me/problems/no/554

解説放送

未定

解説

https://yukicoder.me/submissions/196772

順番にAの要素を計算していくことを考える。
以下に高速にAの1つの要素を計算するかであるが、計算が面倒なのは、奇数番目・偶数番目を足す操作である。
これは、odd,even変数を用意しておき、計算していきながら、そこに足していくことにする。

int N;
mint A[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    mint odd = 0, even = 0;
    A[1] = 1;
    odd = A[1];

    rep(i, 2, N + 1) {
        if (i % 2 == 0) {
            A[i] = odd * i;
            even += A[i];
        } else {
            A[i] = even * i;
            odd += A[i];
        }
    }

    cout << A[N] << endl;
}