Mister雑記

競プロやります。

Codeforces Round #563 (Div. 2) - E 「Ehab and the Expected GCD Problem」 [2500]

codeforces.com

問題

長さ Nの順列 \{ p_i \}に対して、 f(p)を以下のように定める。

  •  g_i = \text{gcd}(p_1, \cdots, p_i)
  •  \{ g_i \}に出現する整数の個数を f(p)とする。

長さ Nの順列 \{ p_i \}のうち、 f(p)が最大となるようなものの個数を求めよ。

制約

  •  2 \leq N \leq 10^6

考察

 N以下の整数で、素因数分解したときに指数の総和が最大となるようなものを Mとする。 この Mについて、各素因数の指数を1ずつ減らしていくような順列のみが f(p)を最大にすることが分かる。 そのような列について、後から余りを挿入していくことを考えれば解けそう。

本番はここで投げてF問題に行ったのだが、コンテスト後のTLで Mの形は 2^n 3 \cdot 2^{n-1}になることを知る。 言われてみればそうと分かるのだが、全然気が付かなかった。


 Mから始まり、隣接する項の比が 2, 3で末尾が 1であるような数列を \{ q_i \}とする。 各 \{ q_i \}について \{ g_i \}を崩さないように要素を挿入することで、全ての条件を満たす順列が得られる。 また異なる \{ q_i \}から得られる順列は全て独立である( \{ g_i \}が異なるため)。 この \{ q_i \}は高々 20個くらいしかないので、これを全探索すればよい。

 \{ q_i \}を1つ固定する。整数 sを挿入することを考えると、 s \bmod q_i \neq 0のときは s q_iの前に挿れることはできない( \{ g_i \}が崩れるため)。 つまり S_i = \{ s \in [ 1, N ] \mid s \bmod q_i = 0, s \bmod q_{i - 1} \neq 0 \}とすると、 S_{i + 1}の全ての要素より前にあるような S_iの要素があってはならない。

 S_{n + 1} \sim S_iの並びを決めたとき、 S_{i - 1}の要素は「先頭は S_{i - 1}の要素である」という制約の元で挿入しなくてはならない。 これは先頭の要素を先に固定することで解決できる。

実装例

codeforces.com

以下では \{ q_i \}ではなくその比の数列を全列挙している。

#include <iostream>
#include <algorithm>
#include <vector>

template <int MOD>
class ModInt {
    ...
};

using namespace std;


using mint = ModInt<1000000007>;

mint calc(const vector<int>& A, int N) {
    vector<bool> used(N + 1, false);
    vector<mint> cnt(A.size(), 0);  // 各集合の要素数

    int prod = 1;
    for (int i = 0; i < A.size(); ++i) {
        prod *= A[i];
        // prodより後に入る要素を挿入
        for (int p = 1; p <= N; ++p) {
            if (!used[p] && p % prod != 0) {
                ++cnt[i];
                used[p] = true;
            }
        }
    }

    mint elem = 0, ret = 1;  // これまでに挿入した要素数、総パターン数
    for (int i = 0; i < A.size(); ++i) {
        // 一番最後の数はcnt[i]通り
        ret *= cnt[i];

        // それ以外の配置は(elem + 1)*...*(elem + cnt[i] - 1)通り
        for (mint n = elem + 1; n < elem + cnt[i]; ++n) {
            ret *= n;
        }
        elem += cnt[i];
    }
    return ret;
}

int main() {
    int N;
    cin >> N;

    int two = 30;
    while (N < (1 << two)) --two;

    mint ans = 0;
    vector<int> A(two, 2);
    ans += calc(A, N);  // M = 2^nの場合

    if ((1 << (two - 1)) * 3 <= N) {  // M = 3 * 2^(n - 1)の場合
        A.back() = 3;
        do {
            ans += calc(A, N);
        } while (next_permutation(A.begin(), A.end()));
    }

    cout << ans << endl;
    return 0;
}

反省

  • う〜ん、1時間あれば解けた気がする...。
    • AC者数に頼りすぎるのも考えもの。
  • 怪文書のような解説になってしまった。
  • DPの方がやりやすいんだろうか。