バチャでは手が回らなかったけど、復習した。ちょっとこの多項式解法は今はよくわからないけど、覚えておこう...

問題概要

$N$ 要素の数列 $a_{1}, \dots, a_{N}$ が与えられる。

$1, 2, \dots, N$ の順列 $p$ に対して、それを巡回群の直積として表したときの、各巡回群に含まれる要素に対応する $a$ の値のうち最小の値の積をとったものを $f(p)$ とおく。

各 $i$ に対して、巡回群の個数が $i$ 個となるような順列 $p$ についての $f(p)$ の積を $b_{i}$ とする。

$b_{1}, \dots, b_{N}$ の最大公約数を mod. 998244353 で求めよ。

制約

$1 \le N \le 10^{5}$

考えたこと

なんだかすごくごっちゃりした設定だけど、最近 AOJ 2378 SolveMe を解き直したこともあって、巡回群来たーーー！！！！！！！！！！！！という気持ちになった。

とりあえず $a$ を小さい順にソートしてしまう！！！
そして巡回群を順に形成していくときに、「まだ選んでないもののうち最小のものを選ぶ」という風に順序を固定しておく。

とりあえず挿入 DP

巡回群を挿入していく DP、要素を 1 個ずつ追加するか、まとめて $k$ 個 (巡回群の位数) を追加するか選択の余地はあるけど、今回は $a$ が小さい順にソートされているので、すでにある巡回群に要素を追加しても変わらない。よって、1 個ずつ追加する形で書いてみよう。

dp[ i ][ j ] := i 個の要素で巡回群を形成していったときに j 個の巡回群ができている場合の、f(p) の積の総和

とする。ここから第1種スターリング数を数え上げるような DP をする。そして、この種の DP では「新たな要素をどの巡回群に加えるか」という視点で考える

dp[ i + 1 ][ j + 1 ] = a[ i ] × dp[ i ][ j ]　(新たな要素で新たな巡回群を作る場合)
dp[ i + 1 ][ j ] = i × dp[ i ][ j ]　(すでにある巡回群に挿入する場合)

という DP になる。a[ i ] = 1 とすれば、第1種スターリング数を求める方法の個数を表す漸化式そのものである。第1種スターリング数に限らず、分割数や (第2種) スターリング数など、グループ分けに関する DP において

新たに追加する要素を新たなグループとするか
新たに追加する要素を既存のグループに挿入するか

で場合分けして DP を組むのは典型的ではある。そして答えは、dp[ N ][ 1 ], dp[ N ][ 2 ], ..., dp[ N ][ N ] の最大公約数なのだが...

dp を多項式化する

これはどうなんだろう...解けている人は実験して導いているのだろうか...

$f_{i}(t)$ = dp[ $i$ ][ 0 ] + dp[ $i$ ][ 1 ] $t$ + dp[ $i$ ][ 2 ] $t^{2}$ + $\dots$

という多項式を考える。ここまでは FFT とかでも見る考え方ではある。なにか詰まったときは機械的にこういう多項式を考えるようにしてもいいかもしれない。DP の遷移

dp[ i + 1 ][ j ] = $a_{i}$ × dp[ i ][ j - 1 ] + i × dp[ i ][ j ]

は機械的に次のようになる。

[ $t^{j}$ ] ( $f^{i+1}$ ) = $a_{i} \times$ [ $t^{j-1}$ ] ( $f^{i}$ ) + $i \times$ [ $t^{j}$ ] ( $f^{j}$ )

そうすると、dp 遷移を次のように解釈できる。

$f_{i+1}$ = $f_{i} \times (a_{i} t + i)$

よって、dp[ N ] は、

$(a_{0}t)(a_{1}t + 1)(a_{2}t + 2) \dots (a_{N-1}t + N-1)$

の各係数になる。こうなると原始多項式に関する理論を適用できる。

原始多項式

原始多項式とは、各係数の最大公約数が 1 であるような多項式のこと。原始多項式同士の積もまた、原始多項式であるという有名な定理がある。このことから、

各係数の最大公約数が $p$ である多項式 $f$ と、各係数の最大公約数が $q$ である多項式 $g$ があるとき、

$fg$ の各係数の最大公約数は $pq$ である

ということがいえる。元の問題に戻って、答えは

${\rm GCD}(a_{0}, 0) \times {\rm GCD}(a_{1}, 1) \times {\rm GCD}(a_{2}, 2) \times \dots \times {\rm GCD}(a_{N-1}, N-1)$

となる。うーん...ここまで自力で解ける気がしないやが ^^;

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MOD = 998244353;

long long GCD(long long x, long long y) {
    if (y == 0) return x;
    else return GCD(y, x % y);
}

int main() {
    int N;
    cin >> N;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    sort(a.begin(), a.end());

    long long res = 1;
    for (int i = 0; i < N; ++i) {
        res = (res * GCD(a[i], i)) % MOD;
    }
    cout << res << endl;
}

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

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

第5回ドワンゴからの挑戦状予選 2018 E - Cyclic GCDs (赤色, 1000 点)

問題概要

制約

考えたこと

とりあえず挿入 DP

dp を多項式化する

原始多項式