ABC349-F Subsequence LCM
(Test/AtCoder/abc349_f.test.cpp)

View this file on GitHub
Last update: 2024-06-30 19:07:00+09:00
Problem: https://atcoder.jp/contests/abc349/tasks/abc349_f

$M$ で割り切れないような要素を部分列に含めると必ず部分列の最小公倍数は $M$ で無くなる。以後 $A$ のすべての要素が $M$ で割り切れることを仮定する。

$M$ を素因数分解して、 $M = \prod p_{i}^{e_{i}}$ という表示を得たとする。この $(p_{i}, e_{i})$ を順に並べた列を $F$ とする。

$A$ のすべての要素が $M$ で割り切れるとして、 $A$ のある部分列の最小公倍数が $M$ とならない必要十分条件は以下の通りである。

ある $F$ の要素 $(p_{i}, e_{i})$ が存在して、部分列のすべての要素が $p_{i}^{e_{i}}$ で割り切れない。

このことから包除原理を適用して数え上げることができる。 $F$ のすべての部分列 $F’$ について $\prod_{i\in F’} p_{i}^{e_{i}}$ で割り切れないように $A$ から部分列を取る通り数を数えれば良い。

$M\le 10^{16}$ ゆえ、 $\mid F \mid \le 13$ である。 $A$ のすべての要素は $M$ で割り切れるという仮定から $A$ の要素の種類数は $43008$ 以下である。

参考: 高度合成数

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc349/tasks/abc349_f"

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/Number/PrimeFactorize.hpp"
#include "atcoder/modint"

#include <iostream>
#include <map>

using namespace zawa;
using mint = atcoder::modint998244353;

int main() {
    SetFastIO(); 

    int N;
    long long M;
    std::cin >> N >> M;
    std::map<long long, int> map;
    int NN{};
    for (int i{} ; i < N ; i++) {
        long long A;
        std::cin >> A;
        if (M % A == 0) {
            map[A]++;
        }
        else {
            NN++;
        }
    }
    N -= NN;
    if (M == 1) {
        std::cout << mint{mint::raw(2).pow(N) - 1}.val() << '\n';
        return 0;
    }
    std::vector A(map.begin(), map.end());
    auto F{PrimeFactorize((unsigned long long)M)};
    std::vector<int> B(A.size());
    for (int i{} ; i < (int)F.size() ; i++) {
        long long mult{1};
        for (int j{} ; j < (int)F[i].exponent() ; j++) {
            mult *= F[i].factor();
        }
        for (int j{} ; j < (int)A.size() ; j++) {
            if (A[j].first % mult == 0) {
                B[j] |= (1 << i);
            }
        }
    }
    std::vector<mint> P2(N + 1, mint::raw(1));
    for (int i{} ; i < N ; i++) {
        P2[i + 1] = P2[i] * mint::raw(2);
    }
    mint ans{P2[N] - 1};
    for (int bit{1} ; bit < (1 << (int)F.size()) ; bit++) {
        int num{};
        for (int i{} ; i < (int)A.size() ; i++) {
            if (B[i] & bit) {
                continue;
            }
            num += A[i].second;
        }
        ans -= (__builtin_popcount(bit) % 2 ? +1 : -1) * (P2[num] - 1);
    }
    std::cout << ans.val() << '\n';
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: atcoder/modint: line -1: no such header

ABC349-F Subsequence LCM (Test/AtCoder/abc349_f.test.cpp)

Depends on

Code

ABC349-F Subsequence LCM
(Test/AtCoder/abc349_f.test.cpp)