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 <math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n elements <math><semantics><mrow><msub><mi>A</mi><mn>1</mn></msub><mo separator="true">,</mo><mo>⋯</mo>&ThinSpace;<mo separator="true">,</mo><msub><mi>A</mi><mi>n</mi></msub></mrow><annotation encoding="application/x-tex">A_1, \cdots, A_n</annotation></semantics></math>A1,⋯,An, there are <math><semantics><mrow><mi>n</mi><mo>!</mo></mrow><annotation encoding="application/x-tex">n!</annotation></semantics></math>n! permutations. For any permutation <math><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math>p, elements with index <math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>i and <math><semantics><mrow><msub><mi>p</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">p_i</annotation></semantics></math>pi is connected and some cycles are formed. Define the beauty of a permutation <math><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math>p the *product* of smallest element in all cycles. And Define <math><semantics><mrow><msub><mi>b</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">b_i</annotation></semantics></math>bi the *sum* of beauty of all permutations that form exactly <math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>i cycles. The task is to calculate GCD of <math><semantics><mrow><msub><mi>b</mi><mn>1</mn></msub><mo separator="true">,</mo><mo>⋯</mo>&ThinSpace;<mo separator="true">,</mo><msub><mi>b</mi><mi>n</mi></msub></mrow><annotation encoding="application/x-tex">b_1, \cdots, b_n</annotation></semantics></math>b1,⋯,bn mod 998244353.

**Constraints:** <math><semantics><mrow><mn>1</mn><mo>≤</mo><mi>n</mi><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup><mo separator="true">,</mo><mn>1</mn><mo>≤</mo><msub><mi>A</mi><mi>i</mi></msub><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>9</mn></msup></mrow><annotation encoding="application/x-tex">1\le n \le 10^5, 1 \le A_i \le 10^9</annotation></semantics></math>1≤n≤105,1≤Ai≤109

## Solution
It is easy to observe that order does not matter, we can sort <math><semantics><mrow><mi>A</mi></mrow><annotation encoding="application/x-tex">A</annotation></semantics></math>A increasingly. Let <math><semantics><mrow><mi>f</mi><mo>(</mo><mi>i</mi><mo separator="true">,</mo><mi>j</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">f(i,j)</annotation></semantics></math>f(i,j) be current <math><semantics><mrow><msub><mi>b</mi><mi>j</mi></msub></mrow><annotation encoding="application/x-tex">b_j</annotation></semantics></math>bj considering the first <math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>i elements of <math><semantics><mrow><mi>A</mi></mrow><annotation encoding="application/x-tex">A</annotation></semantics></math>A, when adding the <math><semantics><mrow><mo>(</mo><mi>i</mi><mo>+</mo><mn>1</mn><mo>)</mo></mrow><annotation encoding="application/x-tex">(i+1)</annotation></semantics></math>(i+1)-th element, there are 2 cases:

1. Add <math><semantics><mrow><msub><mi>A</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub></mrow><annotation encoding="application/x-tex">A_{i+1}</annotation></semantics></math>Ai+1 to any position in any cycle that are formed by previous elements. This will not change the beauty of permutation.
2. <math><semantics><mrow><msub><mi>A</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub></mrow><annotation encoding="application/x-tex">A_{i+1}</annotation></semantics></math>Ai+1 itself forms a new cycle, this will multiply the beauty of permutation by <math><semantics><mrow><msub><mi>A</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub></mrow><annotation encoding="application/x-tex">A_{i+1}</annotation></semantics></math>Ai+1.

The **state-transition equation** is obvious:<math><semantics><mrow><mi>f</mi><mo>(</mo><mi>i</mi><mo>+</mo><mn>1</mn><mo separator="true">,</mo><mi>j</mi><mo>+</mo><mn>1</mn><mo>)</mo><mo>=</mo><mi>i</mi><mo>⋅</mo><mi>f</mi><mo>(</mo><mi>i</mi><mo separator="true">,</mo><mi>j</mi><mo>+</mo><mn>1</mn><mo>)</mo><mo>+</mo><mi>A</mi><mo>[</mo><mi>i</mi><mo>]</mo><mo>⋅</mo><mi>f</mi><mo>(</mo><mi>i</mi><mo separator="true">,</mo><mi>j</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">f(i+1,j+1) = i\cdot f(i, j+1) + A[i] \cdot f(i, j)</annotation></semantics></math>f(i+1,j+1)=i⋅f(i,j+1)+A[i]⋅f(i,j)
However, calculating all <math><semantics><mrow><mi>f</mi><mo>(</mo><mi>n</mi><mo separator="true">,</mo><mi>i</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">f(n,i)</annotation></semantics></math>f(n,i) is of time complexity <math><semantics><mrow><mi>O</mi><mo>(</mo><msup><mi>n</mi><mn>2</mn></msup><mo>)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math>O(n2). It's not affordable.

We can construct such **polynomial**
<math><semantics><mrow><msub><mi>P</mi><mi>i</mi></msub><mo>(</mo><mi>t</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mi>n</mi></munderover><mi>f</mi><mo>(</mo><mi>i</mi><mo separator="true">,</mo><mi>j</mi><mo>)</mo><mo>⋅</mo><msup><mi>t</mi><mi>j</mi></msup></mrow><annotation encoding="application/x-tex">P_i(t)=\sum_{j=0}^n f(i,j)\cdot t^j</annotation></semantics></math>Pi(t)=j=0∑nf(i,j)⋅tj
The transition equation of <math><semantics><mrow><mi>P</mi></mrow><annotation encoding="application/x-tex">P</annotation></semantics></math>P does not depend on <math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math>j
<math><semantics><mrow><msub><mi>P</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>(</mo><mi>t</mi><mo>)</mo><mo>=</mo><mo>(</mo><msub><mi>A</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mi>t</mi><mo>+</mo><mi>i</mi><mo>)</mo><msub><mi>P</mi><mi>i</mi></msub><mo>(</mo><mi>t</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">P_{i+1}(t)=(A_{i+1}t+i)P_i(t)</annotation></semantics></math>Pi+1(t)=(Ai+1t+i)Pi(t)
The 1-shift of <math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math>j in the original dp is convenient to be expressed in the polynomial form (just by multiplying <math><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math>t). The answer is GCD of all coefficients of <math><semantics><mrow><msub><mi>P</mi><mi>n</mi></msub><mo>(</mo><mi>t</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">P_n(t)</annotation></semantics></math>Pn(t) and <math><semantics><mrow><msub><mi>P</mi><mn>0</mn></msub><mo>(</mo><mi>t</mi><mo>)</mo><mo>=</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">P_0(t)=1</annotation></semantics></math>P0(t)=1

Another observation is that: **GCD of coeffients of <math><semantics><mrow><mi>P</mi><mo>⋅</mo><mi>Q</mi></mrow><annotation encoding="application/x-tex">P\cdot Q</annotation></semantics></math>P⋅Q equals to the product of GCD of coefficnets of <math><semantics><mrow><mi>P</mi></mrow><annotation encoding="application/x-tex">P</annotation></semantics></math>P and <math><semantics><mrow><mi>Q</mi></mrow><annotation encoding="application/x-tex">Q</annotation></semantics></math>Q**. Then the answer is <math><semantics><mrow><msubsup><mo>∏</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mi>n</mi></msubsup><mi>g</mi><mi>c</mi><mi>d</mi><mo>(</mo><msub><mi>A</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo separator="true">,</mo><mi>i</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">\prod_{i=0}^n gcd(A_{i+1}, i)</annotation></semantics></math>∏i=0ngcd(Ai+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)

コメント

コメントを投稿