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;
}

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

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