convolution/bostan_mori.cpp

• View this file on GitHub
• Last update: 2025-12-13 22:53:35+09:00

Code

// [x^N] P(x)/Q(x)
// O(K log K log N) (convolution)
// O(K^2 log N) (simple)
// Q[0] = 1, deg(P) < deg(Q) = K
mint bostan_mori(vector<mint> P, const vector<mint>& Q, ll N) {
    // cout << P[0].val() << " " << Q[0].val() << endl;
    if(N == 0) {
        return P[0] / Q[0];
    }

    int K = (int)Q.size();
    P.resize(K - 1);

    vector<mint> minusQ = Q;
    for(int i = 1; i < K; i += 2) {
        minusQ[i] *= -1;
    }

    auto PQ = atcoder::convolution(P, minusQ);
    auto QQ = atcoder::convolution(Q, minusQ);
    // auto PQ = mul(P, minusQ);
    // auto QQ = mul(Q, minusQ);

    vector<mint> nextP(K - 1), nextQ(K);
    for(int i = 0; i < K - 1; i++) {
        nextP[i] = PQ.at(i * 2 + N % 2);
    }
    for(int i = 0; i < K; i++) {
        nextQ[i] = QQ.at(i * 2);
    }

    return bostan_mori(nextP, nextQ, N / 2);
}

#line 1 "convolution/bostan_mori.cpp"


// [x^N] P(x)/Q(x)
// O(K log K log N) (convolution)
// O(K^2 log N) (simple)
// Q[0] = 1, deg(P) < deg(Q) = K
mint bostan_mori(vector<mint> P, const vector<mint>& Q, ll N) {
    // cout << P[0].val() << " " << Q[0].val() << endl;
    if(N == 0) {
        return P[0] / Q[0];
    }

    int K = (int)Q.size();
    P.resize(K - 1);

    vector<mint> minusQ = Q;
    for(int i = 1; i < K; i += 2) {
        minusQ[i] *= -1;
    }

    auto PQ = atcoder::convolution(P, minusQ);
    auto QQ = atcoder::convolution(Q, minusQ);
    // auto PQ = mul(P, minusQ);
    // auto QQ = mul(Q, minusQ);

    vector<mint> nextP(K - 1), nextQ(K);
    for(int i = 0; i < K - 1; i++) {
        nextP[i] = PQ.at(i * 2 + N % 2);
    }
    for(int i = 0; i < K; i++) {
        nextQ[i] = QQ.at(i * 2);
    }

    return bostan_mori(nextP, nextQ, N / 2);
}

Back to top page