2024-02-05

AtCoder ARC 171 D - Rolling Hash (黄色, 600 点)

AtCoder AtCoder600点黄色diff ARC-D 彩色問題グラフ数学(整数問題) 数列構築 Yes/No判定問題区間ほとんどのところで値が一定値に決まる累積和テク:区間の総和を累積和で高速に求める条件の言い換え高速ゼータ変換包除原理 O(3^N)なbitDP bitDP

コンテスト後に解いた。こっちの方が解きやすかった。

問題へのリンク

問題概要

制約

$2 \le P \le 10^{9}$
$1 \le N \le 16$

考えたこと

最初は $B$ の指数を気にするのかな......などと考えていたが、考えていくうちに $B$ の値など、ただの飾りであることがわかってきた。

まず、問題の条件を言い換える。 $B' \equiv B^{-1}$ として、数列 $A$ に対して $C_{i} = A_{i} B'^{i}$ とする。さらに $C$ の累積和を $S$ とする。このとき、問題の条件は、各 $(L_{i}, R_{i})$ に対して

$S_{R_{i}+1} \not\equiv S_{L_{i}} \pmod{P}$

であることと等価であることがわかる。mod $P$ において、 $B$ を自由にかけたり割ったりしても同値性を保てるためだ。

特に、 $P \gt N$ のときは、かならず Yes になる。たとえばすべての区間について条件が課されていたとしても、

$S_{0} \equiv 0$
$S_{1} \equiv 1$
$S_{2} \equiv 2$
$\dots$
$S_{N} \equiv N$

とすればよいためだ。これを満たすような数列 $A$ は容易に逆算できる。

一般の場合

一般の場合であっても、数列 $S$ と数列 $A$ とが一対一に対応することには変わりない。よって、次の条件を満たすように $S_{0}, S_{1}, \dots, S_{N}$ の各値を割り当てることが可能かどうかを判定する問題になったと言える。

数列 $S_{i}$ の各値を $0$ 以上 $P-1$ 以下の値とする
ただし、 $S_{0} \equiv 0$ とする
各 $(L_{i}, R_{i})$ に対して $S_{R_{i}+1} \not\equiv S_{L_{i}}$ となるようにする

これはよく考えると、彩色問題である。頂点 $0, 1, \dots, N$ からなる、 $M$ 本の辺 $(L_{i}, R_{i} + 1)$ を結んだグラフの彩色数を求めて、それが $P$ 以下であるかどうかを判定すればよいのだ。

彩色数は $O(2^{N}N)$ の計算量で求められるアルゴリズムがある。次の記事で解説している。

drken1215.hatenablog.com

コード

//
// 彩色数を求める O(N2^N) のアルゴリズム
//
// cf.
//   https://drken1215.hatenablog.com/entry/2019/01/16/030000
//
// verified
//   ARC 171 D - Rolling Hash
//     https://atcoder.jp/contests/arc171/tasks/arc171_d
//
//   AOJ 2136 Webby Subway
//     http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2136
//


#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();
    }
};

int chromatic_number(const vector<vector<int>> &G) {
    const int MOD = 998244353;
    using mint = Fp<MOD>;
    
    int n = (int)G.size();
    vector<int> neighbor(n, 0);
    for (int i = 0; i < n; ++i) {
        int S = (1<<i);
        for (int j = 0; j < n; ++j) if (G[i][j]) S |= (1<<j);
        neighbor[i] = S;
    }
    
    // I[S] := #. of inndepndet subset of S
    vector<int> I(1<<n);
    I[0] = 1;
    for (int S = 1; S < (1<<n); ++S) {
        int v = __builtin_ctz(S);
        I[S] = I[S & ~(1<<v)] + I[S & ~neighbor[v]];
    }
    int low = 0, high = n;
    while (high - low > 1) {
        int mid = (low + high) >> 1;
        
        // g[S] := #. of "k independent sets" which cover S just
        // f[S] := #. of "k independent sets" which consist of subseta of S
        // then
        //   f[S] = sum_{T in S} g(T)
        //   g[S] = sum_{T in S} (-1)^(|S|-|T|)f[T]
        mint g = 0;
        for (int S = 0; S < (1<<n); ++S) {
            if ((n - __builtin_popcount(S)) & 1) g -= mint(I[S]).pow(mid);
            else g += mint(I[S]).pow(mid);
        }
        if (g != 0) high = mid;
        else low = mid;
    }
    return high;
}

void ARC_171_D() {
    long long P, B, N, M;
    cin >> P >> B >> N >> M;
    
    vector<vector<int>> G(N+1, vector<int>(N+1, 0));
    for (int i = 0; i < M; ++i) {
        int l, r;
        cin >> l >> r;
        --l;
        G[l][r] = G[r][l] = 1;
    }
    if (chromatic_number(G) <= P) cout << "Yes" << endl;
    else cout << "No" << endl;
}

int main() {
    ARC_171_D();
}

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

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

AtCoder ARC 171 D - Rolling Hash (黄色, 600 点)

問題概要

制約

考えたこと

一般の場合

コード