AtCoder Dwango Programming Contest V E.Cyclic GCD (DP+Polynomials)

日付: 11月 25, 2018

[AtCoder - E - Cyclic GCD](https://dwacon5th-prelims.contest.atcoder.jp/tasks/dwacon5th_prelims_e)
## Problem
Given an array of $n$ elements $A_1, \cdots, A_n$, there are $n!$ permutations. For any permutation $p$, elements with index $i$ and $p_i$ is connected and some cycles are formed. Define the beauty of a permutation $p$ the *product* of smallest element in all cycles. And Define $b_i$ the *sum* of beauty of all permutations that form exactly $i$ cycles. The task is to calculate GCD of $b_1, \cdots, b_n$ mod 998244353.

**Constraints:** $1\le n \le 10^5, 1 \le A_i \le 10^9$

## Solution
It is easy to observe that order does not matter, we can sort $A$ increasingly. Let $f(i,j)$ be current $b_j$ considering the first $i$ elements of $A$, when adding the $(i+1)$-th element, there are 2 cases:

1. Add $A_{i+1}$ to any position in any cycle that are formed by previous elements. This will not change the beauty of permutation.
2. $A_{i+1}$ itself forms a new cycle, this will multiply the beauty of permutation by $A_{i+1}$.

The **state-transition equation** is obvious:$$f(i+1,j+1) = i\cdot f(i, j+1) + A[i] \cdot f(i, j)$$
However, calculating all $f(n,i)$ is of time complexity $O(n^2)$. It's not affordable.

We can construct such **polynomial**
$$P_i(t)=\sum_{j=0}^n f(i,j)\cdot t^j$$
The transition equation of $P$ does not depend on $j$
$$P_{i+1}(t)=(A_{i+1}t+i)P_i(t)$$
The 1-shift of $j$ in the original dp is convenient to be expressed in the polynomial form (just by multiplying $t$). The answer is GCD of all coefficients of $P_n(t)$ and $P_0(t)=1$

Another observation is that: **GCD of coeffients of $P\cdot Q$ equals to the product of GCD of coefficnets of $P$ and $Q$**. Then the answer is $\prod_{i=0}^n gcd(A_{i+1}, i)$

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)

const int Mod = 998244353;
int main() {
    int n;
    scanf("%d", &n);
    vector<int> A(n + 1);
    FI(i, 1, n) scanf("%d", &A[i]);
    sort(A.begin() + 1, A.end());
    int ans = A[1] % Mod;
    FI(i, 2, n) ans = 1LL * ans * __gcd(A[i], i - 1) % Mod;
    cout << ans << endl;
}
```

KONGROOの基地

このブログを検索

AtCoder Dwango Programming Contest V E.Cyclic GCD (DP+Polynomials)

コメント

コメントを投稿