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

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

AOJ 3188 Mod Rally (AUPC 2020 day3-D)

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

問題概要

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