2024-05-05

Yosupo Library Checker - Dueue Operate All Composite (2D)

YosupoLibraryChecker NoviSteps2D SWAG クエリ処理問題クエリ:区間一次関数の合成関数の合成クエリ:先頭や末尾の削除クエリ:先頭や末尾への挿入データ構造 deque

SWAG を履修した！

問題へのリンク

問題概要

一次関数の列を考える。初期状態では空である。以下の $Q$ 個のクエリを処理せよ。

クエリタイプ 1 ( $a, b$ )：一次関数 $ax + b$ を列の先頭に挿入する
クエリタイプ 2 ( $a, b$ )：一次関数 $ax + b$ を列の末尾に挿入する
クエリタイプ 3：列の先頭の要素を削除する
クエリタイプ 4：列の末尾の要素を削除する
クエリタイプ 5 ( $x$ )：列を $f_{l}, f_{l+1}, \dots, f_{r-1}$ としたとき、 $\displaystyle f_{r-1}(f_{r-2}(\dots f_{l}(x) \dots))$ の値を 998244353 で割った余りを出力する

制約

$1 \le Q \le 5 \times 10^{5}$

解法

モノイド (セグ木の要件と同じ) の列に対して、以下のクエリに $O(1)$ の計算量で答えられるデータ構造として SWAG がある (参考資料)。

列の末尾に要素 $v$ を挿入する
列の先頭の要素を削除する
現在の列全体の要素についての演算結果を返す

さらに、この仕組みを少し応用することで、queue のような挙動だけでなく、deque のような挙動も実現できる！

Amortize analysis of Deque with 2 Stack from Ken Ogura

www.slideshare.net

今回は、「一次関数の合成」を演算としたモノイド「一次関数」について、上記の処理を施せばよい。具体的には、 $f(x) = ax + b$ , $g(x) = cx + d$ としたとき、

$g(f(x)) = c(ax + b) + d = (ac)x + (bc + d)$

であることから、モノイド (型・演算・単位元) を次のように定めることとした。

// 998244353 で割った余りを管理するデータ構造
const int MOD = 998244353;
using mint = Fp<MOD>;
    
// モノイドの定義
using Monoid = pair<mint,mint>;
auto op = [&](Monoid x, Monoid y) {
    return Monoid(x.first * y.first, x.second * y.first + y.second);
};
Monoid identity = {1, 0};

// SWAG のセットアップ
SWAG<Monoid> sw(op, identity);

あとは、ひたすらクエリに答えればよい。計算量は $O(Q)$ と評価できる。

コード

#include <bits/stdc++.h>
using namespace std;

// SWAG
template<class Monoid> struct SWAG {
    using Func = function<Monoid(Monoid, Monoid)>;
    
    // core member
    Func OP;
    Monoid IDENTITY;
    
    // inner data
    int siz;
    vector<Monoid> dat_left, dat_right, sum_left, sum_right;
    
    // constructor
    SWAG() {}
    SWAG(const Func &op, const Monoid &identity) {
        init(op, identity);
    }
    SWAG(const vector<Monoid> &vec, const Func &op, const Monoid &identity) {
        init(vec, op, identity);
    }
    void init(const Func &op, const Monoid &identity) {
        OP = op;
        IDENTITY = identity;
        clear();
    }
    void init(const vector<Monoid> &vec, const Func &op, const Monoid &identity) {
        init(op, identity);
        for (const auto &v : vec) push_back(v);
    }
    void clear() {
        siz = 0;
        dat_left.clear(), dat_right.clear();
        sum_left = {IDENTITY}, sum_right = {IDENTITY};
    }
    
    // getter
    int size() { return siz; }
    
    // push
    void push_back(const Monoid &v) {
        ++siz;
        dat_right.emplace_back(v);
        sum_right.emplace_back(OP(sum_right.back(), v));
    }
    void push_front(const Monoid &v) {
        ++siz;
        dat_left.emplace_back(v);
        sum_left.emplace_back(OP(v, sum_left.back()));
    }
    
    // pop
    void rebuild() {
        vector<Monoid> tmp;
        for (int i = dat_left.size() - 1; i >= 0; --i) tmp.emplace_back(dat_left[i]);
        for (int i = 0; i < dat_right.size(); ++i) tmp.emplace_back(dat_right[i]);
        clear();
        int mid = tmp.size() / 2;
        for (int i = mid - 1; i >= 0; --i) push_front(tmp[i]);
        for (int i = mid; i < tmp.size(); ++i) push_back(tmp[i]);
        assert(siz == tmp.size());
    }
    void pop_back() {
        if (siz == 1) return clear();
        if (dat_right.empty()) rebuild();
        --siz;
        dat_right.pop_back();
        sum_right.pop_back();
    }
    void pop_front() {
        if (siz == 1) return clear();
        if (dat_left.empty()) rebuild();
        --siz;
        dat_left.pop_back();
        sum_left.pop_back();
    }
    
    // prod
    Monoid prod() {
        return OP(sum_left.back(), sum_right.back());
    }
    
    // debug
    friend ostream& operator << (ostream &s, const SWAG &sw) {
        for (int i = sw.dat_left.size() - 1; i >= 0; --i) s << sw.dat_left[i] << " ";
        for (int i = 0; i < sw.dat_right.size(); ++i) s << sw.dat_right[i] << " ";
        return s;
    }
};

// modint
template<int MOD> struct Fp {
    // inner value
    long long val;
    
    // constructor
    constexpr Fp() : val(0) { }
    constexpr Fp(long long v) : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr long long get() const { return val; }
    constexpr int get_mod() const { return MOD; }
    
    // arithmetic operators
    constexpr Fp operator + () const { return Fp(*this); }
    constexpr Fp operator - () const { return Fp(0) - Fp(*this); }
    constexpr Fp operator + (const Fp &r) const { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp &r) const { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp &r) const { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp &r) const { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp &r) {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp &r) {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp &r) {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp &r) {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp pow(long long n) const {
        Fp res(1), mul(*this);
        while (n > 0) {
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }
    constexpr Fp inv() const {
        Fp res(1), div(*this);
        return res / div;
    }

    // other operators
    constexpr bool operator == (const Fp &r) const {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp &r) const {
        return this->val != r.val;
    }
    constexpr Fp& operator ++ () {
        ++val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -- () {
        if (val == 0) val += MOD;
        --val;
        return *this;
    }
    constexpr Fp operator ++ (int) const {
        Fp res = *this;
        ++*this;
        return res;
    }
    constexpr Fp operator -- (int) const {
        Fp res = *this;
        --*this;
        return res;
    }
    friend constexpr istream& operator >> (istream &is, Fp<MOD> &x) {
        is >> x.val;
        x.val %= MOD;
        if (x.val < 0) x.val += MOD;
        return is;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD> &x) {
        return os << x.val;
    }
    friend constexpr Fp<MOD> pow(const Fp<MOD> &r, long long n) {
        return r.pow(n);
    }
    friend constexpr Fp<MOD> inv(const Fp<MOD> &r) {
        return r.inv();
    }
};

int main() {
    const int MOD = 998244353;
    using mint = Fp<MOD>;
    
    // setup SWAG
    using Monoid = pair<mint,mint>;
    auto op = [&](Monoid x, Monoid y) {
        return Monoid(x.first * y.first, x.second * y.first + y.second);
    };
    Monoid identity = {1, 0};
    SWAG<Monoid> sw(op, identity);
    
    // queries
    int Q;
    scanf("%d", &Q);
    while (Q--) {
        int t, a, b, x;
        scanf("%d", &t);
        if (t == 0) {
            scanf("%d %d", &a, &b);
            sw.push_front(Monoid(a, b));
        } else if (t == 1) {
            scanf("%d %d", &a, &b);
            sw.push_back(Monoid(a, b));
        } else if (t == 2) {
            sw.pop_front();
        } else if (t == 3) {
            sw.pop_back();
        } else {
            scanf("%d", &x);
            auto f = sw.prod();
            int res = (f.first * x + f.second).val;
            printf("%d\n", res);
        }
    }
}

2024-05-05

AtCoder ABC 352 A - AtCoder Line (7Q, 灰色, 100 点)

NoviSteps7Q 算数と数学:不等式を立てる算数と数学易しい算数と数学算数と数学:文字式 if文 Yes/No判定問題易しいYes/No判定問題 AtCoder AtCoder100点 ABC-A 灰色diff 場合分け算数と数学:場合をもれなく列挙する論理演算子「&&」「||」を用いる問題

算数系の問題！

問題へのリンク

問題概要

解法

入力の中に $N$ が含まれるが、これは結局使わない。こういう変数に惑わされないようにしよう。次の 2 つの場合に分けて考える。

$X \lt Y$ のとき (上りのとき)
$X \gt Y$ のとき (下りのとき)

前者の場合は、"Yes" となる条件は $X \lt Z \lt Y$ と書ける。後者の場合は、"Yes" となる条件は $X \gt Z \gt Y$ と書ける。

以上をまとめると、"Yes" であるための条件は次のように書ける。

$X \lt Z \lt Y$ または $X \gt Z \gt Y$

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, X, Y, Z;
    cin >> N >> X >> Y >> Z;
    if (X > Z && Z > Y)
        cout << "Yes" << endl;
    else if (X < Z && Z < Y)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

2024-05-05

Yosupo Library Checker - Queue Operate All Composite (2D)

YosupoLibraryChecker SWAG クエリ処理問題データ構造一次関数の合成関数の合成クエリ:区間クエリ:先頭や末尾の削除クエリ:先頭や末尾への挿入 NoviSteps2D

SWAG を履修した！

問題へのリンク

問題概要

一次関数の列を考える。初期状態では空である。以下の $Q$ 個のクエリを処理せよ。

クエリタイプ 1 ( $a, b$ )：一次関数 $ax + b$ を列の末尾に挿入する
クエリタイプ 2：列の先頭の要素を削除する
クエリタイプ 3 ( $x$ )：列を $f_{l}, f_{l+1}, \dots, f_{r-1}$ としたとき、 $\displaystyle f_{r-1}(f_{r-2}(\dots f_{l}(x) \dots))$ の値を 998244353 で割った余りを出力する

制約

$1 \le Q \le 5 \times 10^{5}$

解法

モノイド (セグ木の要件と同じ) の列に対して、以下のクエリに $O(1)$ の計算量で答えられるデータ構造として SWAG がある (参考資料)。

列の末尾に要素 $v$ を挿入する
列の先頭の要素を削除する
現在の列全体の要素についての演算結果を返す

$g(f(x)) = c(ax + b) + d = (ac)x + (bc + d)$

であることから、モノイド (型・演算・単位元) を次のように定めることとした。

// 998244353 で割った余りを管理するデータ構造
const int MOD = 998244353;
using mint = Fp<MOD>;
    
// モノイドの定義
using Monoid = pair<mint,mint>;
auto op = [&](Monoid x, Monoid y) {
    return Monoid(x.first * y.first, x.second * y.first + y.second);
};
Monoid identity = {1, 0};

// SWAG のセットアップ
SWAG<Monoid> sw(op, identity);

あとは、ひたすらクエリに答えればよい。計算量は $O(Q)$ と評価できる。

コード

#include <bits/stdc++.h>
using namespace std;

// SWAG
template<class Monoid> struct SWAG {
    using Func = function<Monoid(Monoid, Monoid)>;
    
    // core member
    Func OP;
    Monoid IDENTITY;
    
    // inner data
    int siz;
    vector<Monoid> dat_left, dat_right, sum_left, sum_right;
    
    // constructor
    SWAG() {}
    SWAG(const Func &op, const Monoid &identity) {
        init(op, identity);
    }
    SWAG(const vector<Monoid> &vec, const Func &op, const Monoid &identity) {
        init(vec, op, identity);
    }
    void init(const Func &op, const Monoid &identity) {
        OP = op;
        IDENTITY = identity;
        clear();
    }
    void init(const vector<Monoid> &vec, const Func &op, const Monoid &identity) {
        init(op, identity);
        for (const auto &v : vec) push_back(v);
    }
    void clear() {
        siz = 0;
        dat_left.clear(), dat_right.clear();
        sum_left = {IDENTITY}, sum_right = {IDENTITY};
    }
    
    // getter
    int size() { return siz; }
    
    // push
    void push_back(const Monoid &v) {
        ++siz;
        dat_right.emplace_back(v);
        sum_right.emplace_back(OP(sum_right.back(), v));
    }
    void push_front(const Monoid &v) {
        ++siz;
        dat_left.emplace_back(v);
        sum_left.emplace_back(OP(v, sum_left.back()));
    }
    
    // pop
    void rebuild() {
        vector<Monoid> tmp;
        for (int i = dat_left.size() - 1; i >= 0; --i) tmp.emplace_back(dat_left[i]);
        for (int i = 0; i < dat_right.size(); ++i) tmp.emplace_back(dat_right[i]);
        clear();
        int mid = tmp.size() / 2;
        for (int i = mid - 1; i >= 0; --i) push_front(tmp[i]);
        for (int i = mid; i < tmp.size(); ++i) push_back(tmp[i]);
        assert(siz == tmp.size());
    }
    void pop_back() {
        if (siz == 1) return clear();
        if (dat_right.empty()) rebuild();
        --siz;
        dat_right.pop_back();
        sum_right.pop_back();
    }
    void pop_front() {
        if (siz == 1) return clear();
        if (dat_left.empty()) rebuild();
        --siz;
        dat_left.pop_back();
        sum_left.pop_back();
    }
    
    // prod
    Monoid prod() {
        return OP(sum_left.back(), sum_right.back());
    }
    
    // debug
    friend ostream& operator << (ostream &s, const SWAG &sw) {
        for (int i = sw.dat_left.size() - 1; i >= 0; --i) s << sw.dat_left[i] << " ";
        for (int i = 0; i < sw.dat_right.size(); ++i) s << sw.dat_right[i] << " ";
        return s;
    }
};

// modint
template<int MOD> struct Fp {
    // inner value
    long long val;
    
    // constructor
    constexpr Fp() : val(0) { }
    constexpr Fp(long long v) : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr long long get() const { return val; }
    constexpr int get_mod() const { return MOD; }
    
    // arithmetic operators
    constexpr Fp operator + () const { return Fp(*this); }
    constexpr Fp operator - () const { return Fp(0) - Fp(*this); }
    constexpr Fp operator + (const Fp &r) const { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp &r) const { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp &r) const { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp &r) const { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp &r) {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp &r) {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp &r) {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp &r) {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp pow(long long n) const {
        Fp res(1), mul(*this);
        while (n > 0) {
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }
    constexpr Fp inv() const {
        Fp res(1), div(*this);
        return res / div;
    }

    // other operators
    constexpr bool operator == (const Fp &r) const {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp &r) const {
        return this->val != r.val;
    }
    constexpr Fp& operator ++ () {
        ++val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -- () {
        if (val == 0) val += MOD;
        --val;
        return *this;
    }
    constexpr Fp operator ++ (int) const {
        Fp res = *this;
        ++*this;
        return res;
    }
    constexpr Fp operator -- (int) const {
        Fp res = *this;
        --*this;
        return res;
    }
    friend constexpr istream& operator >> (istream &is, Fp<MOD> &x) {
        is >> x.val;
        x.val %= MOD;
        if (x.val < 0) x.val += MOD;
        return is;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD> &x) {
        return os << x.val;
    }
    friend constexpr Fp<MOD> pow(const Fp<MOD> &r, long long n) {
        return r.pow(n);
    }
    friend constexpr Fp<MOD> inv(const Fp<MOD> &r) {
        return r.inv();
    }
};

int main() {
    const int MOD = 998244353;
    using mint = Fp<MOD>;
    
    // setup SWAG
    using Monoid = pair<mint,mint>;
    auto op = [&](Monoid x, Monoid y) {
        return Monoid(x.first * y.first, x.second * y.first + y.second);
    };
    Monoid identity = {1, 0};
    SWAG<Monoid> sw(op, identity);
    
    // queries
    int Q;
    scanf("%d", &Q);
    while (Q--) {
        int t, a, b, x;
        scanf("%d", &t);
        if (t == 0) {
            cin >> a >> b;
            sw.push_back(Monoid(a, b));
        } else if (t == 1) {
            sw.pop_front();
        } else {
            scanf("%d", &x);
            auto f = sw.prod();
            int res = (f.first * x + f.second).val;
            printf("%d\n", res);
        }
    }
}

2024-05-05

AtCoder ABC 352 G - Socks 3 (3D, 橙色, 600 点)

回数の期待値回数の期待値=(k回以上の確率)の和期待値数列二分木のような計算順序分割統治法 FFT 分割統治FFT 高速畳み込み計算多項式・FPS(形式的冪級数) 数学(代数) 中堅以上の典型要素を詰め合わせた教育的問題高度典型 NoviSteps3D AtCoder AtCoder600点橙色diff ABC-G テク:K以上からK+1以上を引く

「回数の期待値」は、(k 回以上の確率) の総和に一致する！！　あとは有名な「 $N$ 個の一次関数の積は二分木のような計算順序で $O(N (\log N)^{2})$ の計算量で求められるという話！

問題へのリンク

問題概要

色が $1, 2, \dots, N$ であるような靴下が $A_{1}, A_{2}, \dots, A_{N}$ 枚ずつある。いずれも 2 種類以上ある。

これらの中からランダムに選ぶことを繰り返す (元には戻さない)。初めて同じ色の靴下が被るようになるまでの引きの回数の期待値を 998244353 で割った余りを求めよ。

制約

$1 \le N \le 3 \times 10^{5}$
$2 \le A_{i} \le 3000$

考えたこと

まず、「〜を達成するまでの回数の期待値」を、次の値に言い換える典型がある！！

(1 回以上を要する確率) + (2 回以上を要する確率) + ...

ここでは、 $k+1$ 回以上を要する確率を $p(k)$ とおく。 $\displaystyle \sum_{k=0}^{N} p(k)$ を求めればよい。

さて、 $p(k)$ は「最初の $k$ 回の色がすべて異なる確率」である。これは、

$S = A_{1} + A_{2} + \dots + A_{N}$
集合 $\{1, 2, \dots, N\}$ の部分集合であって要素数が $k$ であるものからなる集合を $T(k)$

とすると、次のように求められる。

$p(k) = \displaystyle \sum_{\{r_{1}, r_{2}, \dots, r_{k}\} \in T(k)} \frac{k! A_{r_{1}} A_{r_{2}} \dots A_{r_{k}}}{S(S-1)\dots(S-k+1)} = \sum_{\{r_{1}, r_{2}, \dots, r_{k}\} \in T(k)} \frac{A_{r_{1}} A_{r_{2}} \dots A_{r_{k}}}{{}_{S}\rm{C}_{k}}$

いかにも FPS が使える形である。次の多項式 $f$ を考えよう。

$f(x) = (1 + A_{1}x)(1 + A_{2}x) \dots (1 + A_{N}x)$

そうすると、さらに次のようになる。

$p(k) = \displaystyle \frac{\lbrack x^{k} \rbrack f(x)}{{}_{S}\rm{C}_{k}}$

なお、上の多項式 $f$ のように、 $N$ 個の一次式の積を計算するのは、以下の記事に書いたような分割統治法によって $O(N (\log N)^{2})$ の計算量で実行できる。

drken1215.hatenablog.com

以上の解法の全体の計算量も $O(N (\log N)^{2})$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

// modint
template<int MOD> struct Fp {
    // inner value
    long long val;
    
    // constructor
    constexpr Fp() : val(0) { }
    constexpr Fp(long long v) : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr long long get() const { return val; }
    constexpr int get_mod() const { return MOD; }
    
    // arithmetic operators
    constexpr Fp operator + () const { return Fp(*this); }
    constexpr Fp operator - () const { return Fp(0) - Fp(*this); }
    constexpr Fp operator + (const Fp &r) const { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp &r) const { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp &r) const { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp &r) const { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp &r) {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp &r) {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp &r) {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp &r) {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp pow(long long n) const {
        Fp res(1), mul(*this);
        while (n > 0) {
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }
    constexpr Fp inv() const {
        Fp res(1), div(*this);
        return res / div;
    }

    // other operators
    constexpr bool operator == (const Fp &r) const {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp &r) const {
        return this->val != r.val;
    }
    constexpr Fp& operator ++ () {
        ++val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -- () {
        if (val == 0) val += MOD;
        --val;
        return *this;
    }
    constexpr Fp operator ++ (int) const {
        Fp res = *this;
        ++*this;
        return res;
    }
    constexpr Fp operator -- (int) const {
        Fp res = *this;
        --*this;
        return res;
    }
    friend constexpr istream& operator >> (istream &is, Fp<MOD> &x) {
        is >> x.val;
        x.val %= MOD;
        if (x.val < 0) x.val += MOD;
        return is;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD> &x) {
        return os << x.val;
    }
    friend constexpr Fp<MOD> pow(const Fp<MOD> &r, long long n) {
        return r.pow(n);
    }
    friend constexpr Fp<MOD> inv(const Fp<MOD> &r) {
        return r.inv();
    }
};

// Binomial coefficient
template<class mint> struct BiCoef {
    vector<mint> fact_, inv_, finv_;
    constexpr BiCoef() {}
    constexpr BiCoef(int n) : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
        init(n);
    }
    constexpr void init(int n) {
        fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
        int MOD = fact_[0].get_mod();
        for(int i = 2; i < n; i++){
            fact_[i] = fact_[i-1] * i;
            inv_[i] = -inv_[MOD%i] * (MOD/i);
            finv_[i] = finv_[i-1] * inv_[i];
        }
    }
    constexpr mint com(int n, int k) const {
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[k] * finv_[n-k];
    }
    constexpr mint fact(int n) const {
        if (n < 0) return 0;
        return fact_[n];
    }
    constexpr mint inv(int n) const {
        if (n < 0) return 0;
        return inv_[n];
    }
    constexpr mint finv(int n) const {
        if (n < 0) return 0;
        return finv_[n];
    }
};

namespace NTT {
    long long modpow(long long a, long long n, int mod) {
        long long res = 1;
        while (n > 0) {
            if (n & 1) res = res * a % mod;
            a = a * a % mod;
            n >>= 1;
        }
        return res;
    }

    long long modinv(long long a, int mod) {
        long long b = mod, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        u %= mod;
        if (u < 0) u += mod;
        return u;
    }

    int calc_primitive_root(int mod) {
        if (mod == 2) return 1;
        if (mod == 167772161) return 3;
        if (mod == 469762049) return 3;
        if (mod == 754974721) return 11;
        if (mod == 998244353) return 3;
        int divs[20] = {};
        divs[0] = 2;
        int cnt = 1;
        long long x = (mod - 1) / 2;
        while (x % 2 == 0) x /= 2;
        for (long long i = 3; i * i <= x; i += 2) {
            if (x % i == 0) {
                divs[cnt++] = i;
                while (x % i == 0) x /= i;
            }
        }
        if (x > 1) divs[cnt++] = x;
        for (int g = 2;; g++) {
            bool ok = true;
            for (int i = 0; i < cnt; i++) {
                if (modpow(g, (mod - 1) / divs[i], mod) == 1) {
                    ok = false;
                    break;
                }
            }
            if (ok) return g;
        }
    }

    int get_fft_size(int N, int M) {
        int size_a = 1, size_b = 1;
        while (size_a < N) size_a <<= 1;
        while (size_b < M) size_b <<= 1;
        return max(size_a, size_b) << 1;
    }

    // number-theoretic transform
    template<class mint> void trans(vector<mint> &v, bool inv = false) {
        if (v.empty()) return;
        int N = (int)v.size();
        int MOD = v[0].get_mod();
        int PR = calc_primitive_root(MOD);
        static bool first = true;
        static vector<long long> vbw(30), vibw(30);
        if (first) {
            first = false;
            for (int k = 0; k < 30; ++k) {
                vbw[k] = modpow(PR, (MOD - 1) >> (k + 1), MOD);
                vibw[k] = modinv(vbw[k], MOD);
            }
        }
        for (int i = 0, j = 1; j < N - 1; j++) {
            for (int k = N >> 1; k > (i ^= k); k >>= 1);
            if (i > j) swap(v[i], v[j]);
        }
        for (int k = 0, t = 2; t <= N; ++k, t <<= 1) {
            long long bw = vbw[k];
            if (inv) bw = vibw[k];
            for (int i = 0; i < N; i += t) {
                mint w = 1;
                for (int j = 0; j < t/2; ++j) {
                    int j1 = i + j, j2 = i + j + t/2;
                    mint c1 = v[j1], c2 = v[j2] * w;
                    v[j1] = c1 + c2;
                    v[j2] = c1 - c2;
                    w *= bw;
                }
            }
        }
        if (inv) {
            long long invN = modinv(N, MOD);
            for (int i = 0; i < N; ++i) v[i] = v[i] * invN;
        }
    }

    // for garner
    static constexpr int MOD0 = 754974721;
    static constexpr int MOD1 = 167772161;
    static constexpr int MOD2 = 469762049;
    using mint0 = Fp<MOD0>;
    using mint1 = Fp<MOD1>;
    using mint2 = Fp<MOD2>;
    static const mint1 imod0 = 95869806; // modinv(MOD0, MOD1);
    static const mint2 imod1 = 104391568; // modinv(MOD1, MOD2);
    static const mint2 imod01 = 187290749; // imod1 / MOD0;

    // small case (T = mint, long long)
    template<class T> vector<T> naive_mul(const vector<T> &A, const vector<T> &B) {
        if (A.empty() || B.empty()) return {};
        int N = (int)A.size(), M = (int)B.size();
        vector<T> res(N + M - 1);
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < M; ++j)
                res[i + j] += A[i] * B[j];
        return res;
    }

    // mul by convolution
    template<class mint> vector<mint> mul(const vector<mint> &A, const vector<mint> &B) {
        if (A.empty() || B.empty()) return {};
        int N = (int)A.size(), M = (int)B.size();
        if (min(N, M) < 30) return naive_mul(A, B);
        int MOD = A[0].get_mod();
        int size_fft = get_fft_size(N, M);
        if (MOD == 998244353) {
            vector<mint> a(size_fft), b(size_fft), c(size_fft);
            for (int i = 0; i < N; ++i) a[i] = A[i];
            for (int i = 0; i < M; ++i) b[i] = B[i];
            trans(a), trans(b);
            vector<mint> res(size_fft);
            for (int i = 0; i < size_fft; ++i) res[i] = a[i] * b[i];
            trans(res, true);
            res.resize(N + M - 1);
            return res;
        }
        vector<mint0> a0(size_fft, 0), b0(size_fft, 0), c0(size_fft, 0);
        vector<mint1> a1(size_fft, 0), b1(size_fft, 0), c1(size_fft, 0);
        vector<mint2> a2(size_fft, 0), b2(size_fft, 0), c2(size_fft, 0);
        for (int i = 0; i < N; ++i)
            a0[i] = A[i].val, a1[i] = A[i].val, a2[i] = A[i].val;
        for (int i = 0; i < M; ++i)
            b0[i] = B[i].val, b1[i] = B[i].val, b2[i] = B[i].val;
        trans(a0), trans(a1), trans(a2), trans(b0), trans(b1), trans(b2);
        for (int i = 0; i < size_fft; ++i) {
            c0[i] = a0[i] * b0[i];
            c1[i] = a1[i] * b1[i];
            c2[i] = a2[i] * b2[i];
        }
        trans(c0, true), trans(c1, true), trans(c2, true);
        mint mod0 = MOD0, mod01 = mod0 * MOD1;
        vector<mint> res(N + M - 1);
        for (int i = 0; i < N + M - 1; ++i) {
            int y0 = c0[i].val;
            int y1 = (imod0 * (c1[i] - y0)).val;
            int y2 = (imod01 * (c2[i] - y0) - imod1 * y1).val;
            res[i] = mod01 * y2 + mod0 * y1 + y0;
        }
        return res;
    }
};

// Formal Power Series
template<typename mint> struct FPS : vector<mint> {
    using vector<mint>::vector;
 
    // constructor
    constexpr FPS(const vector<mint> &r) : vector<mint>(r) {}
 
    // core operator
    constexpr FPS pre(int siz) const {
        return FPS(begin(*this), begin(*this) + min((int)this->size(), siz));
    }
    constexpr FPS rev() const {
        FPS res = *this;
        reverse(begin(res), end(res));
        return res;
    }
    constexpr FPS& normalize() {
        while (!this->empty() && this->back() == 0) this->pop_back();
        return *this;
    }
 
    // basic operator
    constexpr FPS operator - () const noexcept {
        FPS res = (*this);
        for (int i = 0; i < (int)res.size(); ++i) res[i] = -res[i];
        return res;
    }
    constexpr FPS operator + (const mint &v) const { return FPS(*this) += v; }
    constexpr FPS operator + (const FPS &r) const { return FPS(*this) += r; }
    constexpr FPS operator - (const mint &v) const { return FPS(*this) -= v; }
    constexpr FPS operator - (const FPS &r) const { return FPS(*this) -= r; }
    constexpr FPS operator * (const mint &v) const { return FPS(*this) *= v; }
    constexpr FPS operator * (const FPS &r) const { return FPS(*this) *= r; }
    constexpr FPS operator / (const mint &v) const { return FPS(*this) /= v; }
    constexpr FPS operator / (const FPS &r) const { return FPS(*this) /= r; }
    constexpr FPS operator % (const FPS &r) const { return FPS(*this) %= r; }
    constexpr FPS operator < (const FPS &r) const { return this->size() < r.size(); }
    constexpr FPS operator << (int x) const { return FPS(*this) <<= x; }
    constexpr FPS operator >> (int x) const { return FPS(*this) >>= x; }
    constexpr FPS& operator += (const mint &v) {
        if (this->empty()) this->resize(1);
        (*this)[0] += v;
        return *this;
    }
    constexpr FPS& operator += (const FPS &r) {
        if (r.size() > this->size()) this->resize(r.size());
        for (int i = 0; i < (int)r.size(); ++i) (*this)[i] += r[i];
        return this->normalize();
    }
    constexpr FPS& operator -= (const mint &v) {
        if (this->empty()) this->resize(1);
        (*this)[0] -= v;
        return *this;
    }
    constexpr FPS& operator -= (const FPS &r) {
        if (r.size() > this->size()) this->resize(r.size());
        for (int i = 0; i < (int)r.size(); ++i) (*this)[i] -= r[i];
        return this->normalize();
    }
    constexpr FPS& operator *= (const mint &v) {
        for (int i = 0; i < (int)this->size(); ++i) (*this)[i] *= v;
        return *this;
    }
    constexpr FPS& operator *= (const FPS &r) {
        return *this = NTT::mul((*this), r);
    }
    constexpr FPS& operator /= (const mint &v) {
        assert(v != 0);
        mint iv = modinv(v);
        for (int i = 0; i < (int)this->size(); ++i) (*this)[i] *= iv;
        return *this;
    }
    
    // division, r must be normalized (r.back() must not be 0)
    constexpr FPS& operator /= (const FPS &r) {
        assert(!r.empty());
        assert(r.back() != 0);
        this->normalize();
        if (this->size() < r.size()) {
            this->clear();
            return *this;
        }
        int need = (int)this->size() - (int)r.size() + 1;
        *this = (rev().pre(need) * r.rev().inv(need)).pre(need).rev();
        return *this;
    }
    constexpr FPS& operator %= (const FPS &r) {
        assert(!r.empty());
        assert(r.back() != 0);
        this->normalize();
        FPS q = (*this) / r;
        return *this -= q * r;
    }
    constexpr FPS& operator <<= (int x) {
        FPS res(x, 0);
        res.insert(res.end(), begin(*this), end(*this));
        return *this = res;
    }
    constexpr FPS& operator >>= (int x) {
        FPS res;
        res.insert(res.end(), begin(*this) + x, end(*this));
        return *this = res;
    }
    constexpr mint eval(const mint &v) {
        mint res = 0;
        for (int i = (int)this->size()-1; i >= 0; --i) {
            res *= v;
            res += (*this)[i];
        }
        return res;
    }

    // advanced operation
    // df/dx
    constexpr FPS diff() const {
        int n = (int)this->size();
        FPS res(n-1);
        for (int i = 1; i < n; ++i) res[i-1] = (*this)[i] * i;
        return res;
    }
    
    // \int f dx
    constexpr FPS integral() const {
        int n = (int)this->size();
        FPS res(n+1, 0);
        for (int i = 0; i < n; ++i) res[i+1] = (*this)[i] / (i+1);
        return res;
    }
    
    // inv(f), f[0] must not be 0
    constexpr FPS inv(int deg) const {
        assert((*this)[0] != 0);
        if (deg < 0) deg = (int)this->size();
        FPS res({mint(1) / (*this)[0]});
        for (int i = 1; i < deg; i <<= 1) {
            res = (res + res - res * res * pre(i << 1)).pre(i << 1);
        }
        res.resize(deg);
        return res;
    }
    constexpr FPS inv() const {
        return inv((int)this->size());
    }
    
    // log(f) = \int f'/f dx, f[0] must be 1
    constexpr FPS log(int deg) const {
        assert((*this)[0] == 1);
        FPS res = (diff() * inv(deg)).integral();
        res.resize(deg);
        return res;
    }
    constexpr FPS log() const {
        return log((int)this->size());
    }
    
    // exp(f), f[0] must be 0
    constexpr FPS exp(int deg) const {
        assert((*this)[0] == 0);
        FPS res(1, 1);
        for (int i = 1; i < deg; i <<= 1) {
            res = res * (pre(i << 1) - res.log(i << 1) + 1).pre(i << 1);
        }
        res.resize(deg);
        return res;
    }
    constexpr FPS exp() const {
        return exp((int)this->size());
    }
    
    // pow(f) = exp(e * log f)
    constexpr FPS pow(long long e, int deg) const {
        if (e == 0) {
            FPS res(deg, 0);
            res[0] = 1;
            return res;
        }
        long long i = 0;
        while (i < (int)this->size() && (*this)[i] == 0) ++i;
        if (i == (int)this->size() || i > (deg - 1) / e) return FPS(deg, 0);
        mint k = (*this)[i];
        FPS res = ((((*this) >> i) / k).log(deg) * e).exp(deg) * mint(k).pow(e) << (e * i);
        res.resize(deg);
        return res;
    }
    constexpr FPS pow(long long e) const {
        return pow(e, (int)this->size());
    }
    
    // sqrt(f), f[0] must be 1
    constexpr FPS sqrt_base(int deg) const {
        assert((*this)[0] == 1);
        mint inv2 = mint(1) / 2;
        FPS res(1, 1);
        for (int i = 1; i < deg; i <<= 1) {
            res = (res + pre(i << 1) * res.inv(i << 1)).pre(i << 1);
            for (mint &x : res) x *= inv2;
        }
        res.resize(deg);
        return res;
    }
    constexpr FPS sqrt_base() const {
        return sqrt_base((int)this->size());
    }
    
    // friend operators
    friend constexpr FPS diff(const FPS &f) { return f.diff(); }
    friend constexpr FPS integral(const FPS &f) { return f.integral(); }
    friend constexpr FPS inv(const FPS &f, int deg) { return f.inv(deg); }
    friend constexpr FPS inv(const FPS &f) { return f.inv((int)f.size()); }
    friend constexpr FPS log(const FPS &f, int deg) { return f.log(deg); }
    friend constexpr FPS log(const FPS &f) { return f.log((int)f.size()); }
    friend constexpr FPS exp(const FPS &f, int deg) { return f.exp(deg); }
    friend constexpr FPS exp(const FPS &f) { return f.exp((int)f.size()); }
    friend constexpr FPS pow(const FPS &f, long long e, int deg) { return f.pow(e, deg); }
    friend constexpr FPS pow(const FPS &f, long long e) { return f.pow(e, (int)f.size()); }
    friend constexpr FPS sqrt_base(const FPS &f, int deg) { return f.sqrt_base(deg); }
    friend constexpr FPS sqrt_base(const FPS &f) { return f.sqrt_base((int)f.size()); }
};

const int MOD = 998244353;
using mint = Fp<MOD>;

int main() {
    long long N, sum = 0;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i], sum += A[i];
    
    vector<FPS<mint>> pols(N);
    vector<mint> com(N + 1, 1);
    for (int i = 0; i < N; ++i) {
        com[i+1] = com[i] * (sum - i) / (i + 1);
        pols[i] = {1, A[i]};
    }
    
    auto rec = [&](auto rec, int left, int right) -> FPS<mint> {
        if (right - left == 1) return pols[left];
        int mid = (left + right) / 2;
        auto lv = rec(rec, left, mid);
        auto rv = rec(rec, mid, right);
        return lv * rv;
    };
    auto func = rec(rec, 0, N);
    
    mint res = 0;
    for (int k = 0; k <= N; ++k) res += func[k] / com[k];
    cout << res << endl;
}

2024-05-04

JOI 一次予選 2024 (第 2 回) B - 火曜日 (8Q, 難易度 1)

算数と数学:条件を筋よく整理する算数と数学易しい算数と数学数学(整数問題) 易しい整数問題演算子「/」「%」を用いる問題 JOI AtCoder JOI一次予選 if文 JOI難易度1 周期性に着目する日付や時刻に関する問題 Yes/No判定問題易しいYes/No判定問題

慣れていないと少し難しいかもしれない。

問題概要

今日は日曜日である。

今日の $X$ 日後が火曜日であるならば 1 を、そうでないならば 0 を出力せよ。

解法

$X$ 日後が火曜日であるための条件を考えましょう。

「0 日後は日曜日」「1 日後は月曜日」「2 日後は火曜日」...といった情報を整理すると、下図のようになります。

火曜日のところに注目すると、

$X = 2, 9, 16, 23, 30, \dots$

となっていることが分かります。これらの値の特徴は何かわかるでしょうか。それは

$X$ を 7 で割った余りが 2 であること

です。整数値 X を 7 で割った余りは X % 7 と書けるのですから、この問題は次のようにして解けます。

X % 7 == 2 であるとき：1 を出力する
X % 7 != 2 であるとき：0 を出力する

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int X;
    cin >> X;
    if (X % 7 == 2)
        cout << 1 << endl;
    else
        cout << 0 << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Yosupo Library Checker - Dueue Operate All Composite (2D)

問題概要

制約

解法

コード

AtCoder ABC 352 A - AtCoder Line (7Q, 灰色, 100 点)

問題概要

解法

コード

Yosupo Library Checker - Queue Operate All Composite (2D)

問題概要

制約

解法

コード

AtCoder ABC 352 G - Socks 3 (3D, 橙色, 600 点)

問題概要

制約

考えたこと

コード

JOI 一次予選 2024 (第 2 回) B - 火曜日 (8Q, 難易度 1)

問題概要

解法

コード