This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ei1333/library
#include "math/fps/coeff-of-rational-function.hpp"
$K$ 次多項式 $P(x), Q(x)$ に対して $\displaystyle [x^N] \frac{P(x)}{Q(x)}$ を Bostan-Mori algorithm によって計算する。
$O(K \log K \log N)$
/** * @brief Coeff of Rational Function * @docs docs/coeff-of-rational-function.md */ template< template< typename > class FPS, typename Mint > Mint coeff_of_rational_function(FPS< Mint > P, FPS< Mint > Q, int64_t k) { // compute the coefficient [x^k] P/Q of rational power series Mint ret = 0; if(P.size() >= Q.size()) { auto R = P / Q; P -= R * Q; P.shrink(); if(k < (int) R.size()) ret += R[k]; } if(P.empty()) return ret; P.resize((int) Q.size() - 1); auto sub = [&](const FPS< Mint > &as, bool odd) { FPS< Mint > bs((as.size() + !odd) / 2); for(int i = odd; i < (int) as.size(); i += 2) bs[i >> 1] = as[i]; return bs; }; while(k > 0) { auto Q2(Q); for(int i = 1; i < (int) Q2.size(); i += 2) Q2[i] = -Q2[i]; P = sub(P * Q2, k & 1); Q = sub(Q * Q2, 0); k >>= 1; } return ret + P[0]; }
#line 1 "math/fps/coeff-of-rational-function.hpp" /** * @brief Coeff of Rational Function * @docs docs/coeff-of-rational-function.md */ template< template< typename > class FPS, typename Mint > Mint coeff_of_rational_function(FPS< Mint > P, FPS< Mint > Q, int64_t k) { // compute the coefficient [x^k] P/Q of rational power series Mint ret = 0; if(P.size() >= Q.size()) { auto R = P / Q; P -= R * Q; P.shrink(); if(k < (int) R.size()) ret += R[k]; } if(P.empty()) return ret; P.resize((int) Q.size() - 1); auto sub = [&](const FPS< Mint > &as, bool odd) { FPS< Mint > bs((as.size() + !odd) / 2); for(int i = odd; i < (int) as.size(); i += 2) bs[i >> 1] = as[i]; return bs; }; while(k > 0) { auto Q2(Q); for(int i = 1; i < (int) Q2.size(); i += 2) Q2[i] = -Q2[i]; P = sub(P * Q2, k & 1); Q = sub(Q * Q2, 0); k >>= 1; } return ret + P[0]; }