test/aoj/alds1/kitamasa.test.cpp

AC · 最終更新 2026-09-07 · GitHub

問題: https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_10_A

依存するヘッダ（8）

NTT・畳み込み (convolution) lib/convolution/ntt.hpp
Montgomery + AVX2 による NTT 畳み込み (NTT-friendly な 32bit 素数 mod 専用) lib/convolution/ntt_avx2.hpp
internal/internal_fft.hpp lib/internal/internal_fft.hpp
internal/internal_fft_avx2.hpp lib/internal/internal_fft_avx2.hpp
internal/internal_math.hpp lib/internal/internal_math.hpp
internal/internal_type_traits.hpp lib/internal/internal_type_traits.hpp
きたまさ法（任意可換環版、$O(k^2 \log n)$） lib/linalg/linear_recurrence.hpp
modint (static_modint / dynamic_modint) lib/number_theory/modint.hpp

実装

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_10_A
#include <cstdint>
#include <iostream>
#include <vector>
#include "linalg/linear_recurrence.hpp"

int main(void) {
    int n;
    std::cin >> n;
    std::vector<std::int64_t> a(2, 1), d(2, 1);
    std::cout << kitamasa(a, d, n) << '\n';

    return 0;
}