This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub maspypy/library
#include "linalg/blackbox/det.hpp"
#include "linalg/blackbox/min_poly.hpp" template <typename mint, typename F> mint blackbox_det(int N, F apply) { vc<mint> c(N); FOR(i, N) c[i] = RNG(1, mint::get_mod()); mint r = 1; FOR(i, N) r *= c[i]; auto g = [&](vc<mint> v) -> vc<mint> { FOR(i, N) v[i] *= c[i]; return apply(v); }; auto f = blackbox_min_poly<mint>(N, g); mint det = (len(f) == N + 1 ? f[0] : mint(0)); if (N & 1) det *= -1; det /= r; return det; }
#line 2 "seq/find_linear_rec.hpp" template <typename mint> vector<mint> find_linear_rec(vector<mint>& A) { int N = len(A); vc<mint> B = {1}, C = {1}; int l = 0, m = 1; mint p = 1; FOR(i, N) { mint d = A[i]; FOR3(j, 1, l + 1) { d += C[j] * A[i - j]; } if (d == 0) { ++m; continue; } auto tmp = C; mint q = d / p; if (len(C) < len(B) + m) C.insert(C.end(), len(B) + m - len(C), 0); FOR(j, len(B)) C[j + m] -= q * B[j]; if (l + l <= i) { B = tmp; l = i + 1 - l, m = 1; p = d; } else { ++m; } } return C; } #line 2 "random/base.hpp" u64 RNG_64() { static uint64_t x_ = uint64_t(chrono::duration_cast<chrono::nanoseconds>( chrono::high_resolution_clock::now().time_since_epoch()) .count()) * 10150724397891781847ULL; x_ ^= x_ << 7; return x_ ^= x_ >> 9; } u64 RNG(u64 lim) { return RNG_64() % lim; } ll RNG(ll l, ll r) { return l + RNG_64() % (r - l); } #line 3 "linalg/blackbox/min_poly.hpp" // 行列 A をかけることを表す線形変換 f を渡す // auto f = [&](vc<mint> v) -> vc<mint> {}; template <typename mint, typename F> vc<mint> blackbox_min_poly(int N, F f) { vc<mint> S(N + N + 10); vc<mint> c(N); vc<mint> v(N); FOR(i, N) c[i] = RNG(0, mint::get_mod()); FOR(i, N) v[i] = RNG(0, mint::get_mod()); FOR(k, N + N + 10) { FOR(i, N) S[k] += c[i] * v[i]; v = f(v); } S = find_linear_rec(S); reverse(all(S)); return S; } #line 2 "linalg/blackbox/det.hpp" template <typename mint, typename F> mint blackbox_det(int N, F apply) { vc<mint> c(N); FOR(i, N) c[i] = RNG(1, mint::get_mod()); mint r = 1; FOR(i, N) r *= c[i]; auto g = [&](vc<mint> v) -> vc<mint> { FOR(i, N) v[i] *= c[i]; return apply(v); }; auto f = blackbox_min_poly<mint>(N, g); mint det = (len(f) == N + 1 ? f[0] : mint(0)); if (N & 1) det *= -1; det /= r; return det; }