2020-09-22

AOJ 3188 Mod Rally (AUPC 2020 day3-D)

AOJ ACPC グラフ数学(整数問題) 素因数分解 DP 最短路問題 Yes/No判定問題必要条件を列挙したら十分条件になる原始根シーケンシャルDP 位数の法則強連結成分を考える強連結成分分解

最初誤読して、「何度でもスタート地点にワープして戻っても良い」というバージョンの問題を解いていた。

問題概要

$N$ 個の整数 $a_{1}, \dots, a_{N}$ と 2 以上の整数 $M$ が与えられる。 $M$ 頂点からなる以下のような有向グラフであって、頂点 1 を始点として、頂点 $0, 1, \dots, M-1$ をすべて訪れるようなウォークが存在するかどうかを判定せよ。

各頂点 $u$ に対して、 $u \times a_{i} = v$ となるような $i$ が存在するとき、有向辺 $(u, v)$ が張られている

制約

$N, M \le 2000$

解法 (1)：純粋にグラフの問題として解く

想定解法はこちらだった。

強連結成分分解する (各連結成分内では自由に行き来できる)
頂点 1 を含む連結成分から各連結成分への最長路 (DAG なので DP でできる) を求める
その値が、DAG の辺数に等しければ Yes、そうでなければ No

計算量は $O(NM)$ 。

解法 (2)：整数論的考察する

最初誤読して、「個数制限なしナップサック問題」かと勘違いしてしまった。しかし、一度頂点を出発したら、引き返せない設定だと気づいた。

さて、そうとなれば $M$ を素因数分解したときに、複数の素因数を持つ場合はダメ。たとえば $M = 12$ としたとき、

頂点 2 に訪れるよりも先に頂点 3 を訪れてしまったならば、それ以降は 3 の倍数にしかならないので、頂点 2 へ行くのは不可能
頂点 3 に訪れるよりも先に頂点 2 を訪れてしまったならば、それ以降は 2 の倍数にしかならないので、頂点 3 へ行くのは不可能

という感じだ。一般に、M が相異なる素数 $p, q$ でともに割り切れるとき、頂点 $p, q$ に両方とも行くことは不可能なのだ。

M が素数べきのとき

こうして問題は、 $M$ が素数べきの場合のみに限られた。この場合は次のようになる。

$M$ と互いに素な整数をすべて作れなければ明らかにダメ
$M = p^{e}$ としたとき、ある $A_{i}$ が存在して、 ${\rm GCD}(A_{i}, M) = p$ でなければダメ (これを $b$ とする)

ということが言える。逆にこれらを満たせばすべて作ることができる。具体的には次のようにする。

まず $M$ と互いに素な整数をすべて作る (1 に戻ってこれる)、そして頂点 1 に戻ってくる
頂点 1 から、頂点 $b$ へと遷移する。ここから、ふたたび $M$ と互いに素な整数を順にかけていく。こうすることで、 $M$ との最大公約数が $p$ であるような頂点をすべて行き渡る。そして頂点 $p$ に戻ってくる
頂点 $p$ から、頂点 $p^{2}$ へと遷移する。ここから同様にして、 $M$ との最大公約数が $p^{2}$ であるような頂点をすべて行き渡ることができる。そして頂点 $p^{2}$ に戻ってくる
以下同様

M と互いに素な整数をすべて作れるか

$M$ との最大公約数が $p$ であるような元が存在するかどうかを判定するのは簡単。残りは、 $M$ と互いに素な整数をすべて作れるかどうかを判定する部分。

実はこうなったらもうナップサック問題でやってもいい。なぜなら、 $M$ と互いに素な整数 $a$ に対してはオイラーの定理から

$a^{\phi(M)} ≡ 1 \pmod M$

が成立するので、 $a$ を何回もかけていたらいつかは 1 に戻るのだ。よって、 $M$ と互いに素な整数をかけているうちは、いつでも 1 に戻ってこれるので、ナップサック問題と考えて OK。具体的には

$M$ と互いに素であるような各 $a_{i}$ に対して、その冪乗のとりうる値を求める
それらを併合したものを作る (高々 $M$ 個になる)
それらでナップサック問題を解く

という風にした。さらに、

$A_{1}, \dots, A_{N}$ のうち、 $M$ と互いに素な整数を選んでかけることで $M$ と互いに素な剰余をすべて作れる
$M$ との最大公約数が $p$ であるような元が存在する

ということと

$A_{1}, \dots, A_{N}$ から選んでかけることで $M$ の剰余をすべて作れる

ということは同値なので、まとめてやった。計算量は $O((N+M)M)$ 。

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

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

bool solve() {
    int N, M;
    cin >> N >> M;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i], a[i] %= M;

    // 素因数が複数個あったらダメ
    auto pf = prime_factorize(M);
    if (pf.size() >= 2) return false;

    // a[i] の冪乗でできるものを列挙
    set<long long> se;
    for (int i = 0; i < N; ++i) {
        set<long long> tmp;
        long long cur = a[i];
        while (!tmp.count(cur)) {
            tmp.insert(cur);
            cur = (cur * a[i]) % M;
        }
        for (auto it : tmp) se.insert(it);
    }

    // ナップサック
    vector<bool> dp(M, false), ndp;
    dp[1] = true;
    for (auto it : se) {
        ndp.assign(M, false);
        for (long long j = 0; j < M; ++j) {
            if (!dp[j]) continue;
            ndp[j] = true;
            ndp[(j * it) % M] = true;
        }
        swap(dp, ndp);
    }
    for (int j = 0; j < M; ++j) if (!dp[j]) return false;
    return true;
}

int main() {
    if (solve()) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

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