---
tags: DDJRC
---

# DDJ Regular Contest Round#5 Tutorial

## a626: A. 簽到
<code>tags: geometry</code>

#### 結論: 三個有向面積$\overrightarrow{PA}\times\overrightarrow{PB},\ \overrightarrow{PB}\times\overrightarrow{PC},\ \overrightarrow{PC}\times\overrightarrow{PA}$同號等價於$P$在三角形內
自己畫幾張圖觀察一下三個面積的方向就會發現這很顯然
這裡簡單證明一下，不管$P$在哪裡$\triangle ABC$的面積都可以寫成
$$\frac{1}{2}\left|\overrightarrow{PA}\times\overrightarrow{PB}+\overrightarrow{PB}\times\overrightarrow{PC}+\overrightarrow{PC}\times\overrightarrow{PA}\right|$$
如果$P$在$\triangle ABC$內面積可以寫成
$$\frac{1}{2}\left|\overrightarrow{PA}\times\overrightarrow{PB}\right|+\frac{1}{2}\left|\overrightarrow{PB}\times\overrightarrow{PC}\right|+\frac{1}{2}\left|\overrightarrow{PC}\times\overrightarrow{PA}\right|$$
如果$P$在$\triangle ABC$外，則上式會大於$\triangle ABC$的面積
這足以證明 **$P$在$\triangle ABC$內**是**三個有向面積同號**的充分必要條件

:::spoiler Solution

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;
using pll = pair<long long, long long>;

inline pll operator-(const pll &a, const pll &b) { return {a.ff - b.ff, a.ss - b.ss}; }
inline long long operator^(pll a, pll b) { return a.ff * b.ss - a.ss * b.ff; }
inline int sig(long long x) { return (x > 0) - (x < 0); }

void solve() {
    pll p, a, b, c;
    cin >> p.ff >> p.ss;
    cin >> a.ff >> a.ss >> b.ff >> b.ss >> c.ff >> c.ss;
    int t = sig((a-p)^(b-p)) + sig((b-p)^(c-p)) + sig((c-p)^(a-p));
    if (t == 3 || t == -3) cout << "YES\n";
    else cout << "NO\n";
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

:::

---

## a622: B. 關燈遊戲
<code>tags: greedy, number theory</code>

#### 結論: 一直操作編號最大的亮燈直到全滅

兩個顯然的性質
1. 操作順序不影響結果
2. 操作兩次等於不操作，所以規定每盞燈最多操作一次

假設目前編號最大的亮燈是$p$，根據$1.$我們可以先來考慮如何把$p$滅掉，想要把$p$滅掉可以對$p$的任意一個倍數操作，將$p$的倍數分成$p$和$kp\ (k\ge2)$討論，如果選擇操作$kp$，則最大的亮燈變為$kp$，現在討論如何滅掉$kp$，但根據$2.$我們不能再對$kp$操作，只能在選擇一個更大的倍數操作，最大的亮燈編號將會不斷變大永遠無法全滅，因此只能選擇操作$p$使最大的亮燈編號不斷變小直到全滅

實作的部分可以從大到小暴力枚舉因數操作，時間複雜度$O(n\sqrt{n})$
也可以枚舉每個數的倍數求出哪些數的因數包含自己並記錄起來，時間和空間複雜度都是$O(n\log n)$
###### 註: 調和級數的複雜度是$O(\log n)$

一個比較乾淨的作法是從大到小枚舉每個數$i$的倍數去計算$i$改變了幾次，在處理到$i$之前，$sta[i]$的定義是亮/暗(0/1)，處理完$i$後$sta[i]$的定義變成操作/不操作(0/1)，時間複雜度$O(n\log n)$

:::spoiler Solution

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

bool sta[maxn];

void solve() {
    int n, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> sta[i];
    for (int i = n; i; i--) {
        for (int j = i+i; j <= n; j += i)
            sta[i] ^= sta[j];
        ans += sta[i];
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

:::

---

## a625: C. 括號序列
<code>tags: data structures</code>

如果把`(`當$+1$`)`當$-1$，一個合法的序列要滿足
1. 和為$0$，`(`的數量要等於`)`的數量
2. 任何一個前綴和都要$\ge0$，`(`的數量要大於等於`)`的數量

於是維護前綴和
對於詢問$[l, r]$需要判斷是否有$sum[r]-sum[l-1]=0$和$min(sum[l],sum[l+1],...,sum[r])-sum[l-1]\ge0$
對於修改$i$需要將$sum[i]\sim sum[n]$$\ +2$或$-2$
### Subtask 1 (30%)
暴力
### Subtask 2 (70%)
維護一個區間最小區間加值線段樹

:::spoiler Solution

#include <bits/stdc++.h>

using namespace std;

const int maxn = 4e5 + 5;

int sum[maxn];
string str;

struct segment_tree {
    static const int maxn = 16e5 + 5;
    int mi[maxn] = {}, tag[maxn] = {};
    inline void updata(int p, int v) { mi[p] += v, tag[p] += v; }
    inline void pull(int p) { mi[p] = min(mi[p<<1], mi[p<<1|1]) + tag[p]; }
    inline void push(int p) {
        if (tag[p]) updata(p<<1, tag[p]), updata(p<<1|1, tag[p]);
        tag[p] = 0;
    }
    void build(int l, int r, int p) {
        if (l == r) { mi[p] = sum[l]; return; }
        int mid = (l+r)>>1;
        build(l, mid, p<<1), build(mid+1, r, p<<1|1);
        pull(p);
    }
    int query(int l, int r, int ql, int qr, int p) {
        if (ql == 0) return 0;
        if (ql == l && qr == r) return mi[p];
        push(p);
        int mid = (l+r)>>1;
        if (qr <= mid) return query(l, mid, ql, qr, p<<1);
        else if (mid < ql) return query(mid+1, r, ql, qr, p<<1|1);
        else return min(query(l, mid, ql, mid, p<<1), query(mid+1, r, mid+1, qr, p<<1|1));   
    }
    void modify(int l, int r, int ml, int mr, int v, int p) {
        if (ml == l && mr == r) { updata(p, v); return; }
        int mid = (l+r)>>1;
        push(p);
        if (mr <= mid) modify(l, mid, ml, mr, v, p<<1);
        else if (mid < ml) modify(mid+1, r, ml, mr, v, p<<1|1);
        else modify(l, mid, ml, mid, v, p<<1), modify(mid+1, r, mid+1, mr, v, p<<1|1);
        pull(p);
    }
} seg;

void solve() {
    int n, m;
    cin >> n >> m;
    cin >> str;
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i-1] + 1 - 2*(str[i-1] == ')');
    seg.build(1, n, 1);
    int opt, l, r;
    while (m--) {
        cin >> opt;
        if (opt == 1) {
            cin >> l >> r;
            if ((r-l+1)&1) cout << "NO\n";
            else if (seg.query(1, n, r, r, 1) != seg.query(1, n, l-1, l-1, 1))
                cout << "NO\n";
            else if (seg.query(1, n, l, r, 1) - seg.query(1, n, l-1, l-1, 1) >= 0)
                cout << "YES\n";
            else cout << "NO\n";
        }
        else if (opt == 2) {
            cin >> l;
            if (str[l-1] == '(') {
                str[l-1] = ')';
                seg.modify(1, n, l, n, -2, 1);
            }
            else {
                str[l-1] = '(';
                seg.modify(1, n, l, n, 2, 1);
            }
        }
    }
}

signed main() {
    solve();
    return 0;
}

:::

---

## a621: D. 樹的分數
<code>tags: trees, combinatorics, math</code>

考慮直接算出原樹的分數，用$cnt_u$表示包含節點$u$的路徑個數，則節點$u$對分數的貢獻就是$u\times cnt_u$，根據[排序不等式](https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E4%B8%8D%E7%AD%89%E5%BC%8F)，只要將小的編號配小的權重，大的編號配大的權重就可以有最大分數
### Subtask 1 (15%)
顯然越靠近重心$cnt$越大，越靠近葉子$cnt$越小，且從一邊數來第$k$個節點和從另一邊數來第$k$個節點的$cnt$一樣，也就是這兩個節點的編號交換不影響分數，因此答案就是$2^{\left \lfloor \frac{n}{2} \right \rfloor}$
### Subtask 2 (25%)

現在必須算出每個$cnt$的值，以$u$為根包含$u$的路徑有兩種，起點或終點為$u$，和起點在$u$的某個子數上終點在$u$的另一個子樹上，所以有
$$cnt_u=(n-1)+\sum_{i=1}^{d_u-1} \sum_{j=i+1}^{d_u} siz[v_i]\times siz[v_j]$$
其中$d_u$表示點$u$的度數，$v_i$表示$u$的第$i$個鄰居，$siz[v_i]$表示子樹的大小，若同樣的$cnt$值有$k$個，則這$k$個節點的編號可以互換，對答案貢獻$k!$，暴力計算$cnt$的複雜度為$O(\sum d_i^2)=O(n^2)$

### Subtask 3 (60%)
只要將Subtask2的求法優化一下即可，注意到$$2\sum_{i=1}^{d-1} \sum_{j=i+1}^{d} siz[v_i]\times siz[v_j]=(\sum_{i=1}^{d} siz[v_i])^2-\sum_{i=1}^{d} siz[v_i]^2=(n-1)^2-\sum_{i=1}^{d} siz[v_i]^2$$
或者換一種計算方法，全部路徑扣掉起點終點都在同一個子樹的路徑
$$cnt_u=C_2^n-\sum_{i=1}^{d_u} C_2^{siz[v_i]}$$
這樣複雜度變為$O(\sum d)=O(n)$

:::spoiler Solution

#include <bits/stdc++.h>

using namespace std;

const long long mod = 998244353;
const int maxn = 2e5 + 5;

map<long long, int> cnt;
long long fac[maxn];
vector<int> G[maxn];
int n;

long long dfs(int u, int f) {
    long long ret = 1, t;
    long long s = 1ll * n * (n-1) / 2;
    for (int v : G[u]) {
        if (v == f) continue;
        t = dfs(v, u);
        s -= t * (t-1) / 2;
        ret += t;
    }
    s -= (n-ret) * (n-ret-1) / 2;
    cnt[s]++;
    return ret;
}

void solve() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs(1, 0);
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = fac[i-1] * i % mod;
    long long ans = 1;
    for (pair<long long, int> p : cnt)
        ans = ans * fac[p.second] % mod;
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

:::

---

## a614: E. 數列貼貼
<code>tags: dp, math, matrices</code>
### Subtask 1 (20%)
暴力遞推
### Subtask 2 (80%)
將$a_{i+1}a_i$展開
$$a_{i+1}a_i=(xa_i+ya_{i-1})(xa_{i-1}+ya_{i-2})=x^2a_ia_{i-1}+xya_ia_{i-2}+xya_{i-1}a_{i-1}+y^2a_{i-1}a_{i-2}$$現在嘗試湊出從$\vec v_i=(a_ia_{i-1},a_ia_{i-2},a_{i-1}a_{i-1},a_{i-1}a_{i-2})$到$\vec v_{i+1}=(a_{i+1}a_i,a_{i+1}a_{i-1},a_ia_i,a_ia_{i-1})$
的線性轉移

$\qquad\qquad\qquad a_{i+1}a_i=(x^2,xy,xy,y^2)\cdot \vec v_i$
$\qquad\qquad\qquad a_{i+1}a_{i-1}=(xa_i+ya_{i-1})a_{i-1}=xa_ia_{i-1}+ya_{i-1}a_{i-1}=(x,0,y,0)\cdot \vec v_i$
$\qquad\qquad\qquad a_{i}a_{i}=a_i(xa_{i-1}+ya_{i-2})=xa_ia_{i-1}+ya_{i}a_{i-2}=(x,y,0,0)\cdot \vec v_i$
$\qquad\qquad\qquad a_ia_{i-1}=(1,0,0,0)\cdot \vec v_i$

所以轉移方程為
$$
\begin{bmatrix}
x^2 & xy & xy & y^2 \\
x & 0 & y & 0 \\
x & y & 0 & 0 \\
1 & 0 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
a_ia_{i-1} \\
a_ia_{i-2} \\
a_{i-1}a_{i-1} \\
a_{i-1}a_{i-2} \\
\end{bmatrix}
=\begin{bmatrix}
a_{i+1}a_{i} \\
a_{i+1}a_{i-1} \\
a_{i}a_{i} \\
a_{i}a_{i-1} \\
\end{bmatrix}
$$再設$S_i=a_1a_2+a_2a_3+...+a_{i-2}a_{i-1}$加入轉移式
$$
\begin{bmatrix}
x^2 & xy & xy & y^2 & 0 \\
x & 0 & y & 0 & 0 \\
x & y & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
a_ia_{i-1} \\
a_ia_{i-2} \\
a_{i-1}a_{i-1} \\
a_{i-1}a_{i-2} \\
S_i \\
\end{bmatrix}
=\begin{bmatrix}
a_{i+1}a_{i} \\
a_{i+1}a_{i-1} \\
a_{i}a_{i} \\
a_{i}a_{i-1} \\
S_{i+1} \\
\end{bmatrix}
$$用矩陣快速冪求$\vec v_{n+1}$，時間複雜度$O(5^3\log n)$
:::spoiler Solution

#include <bits/stdc++.h>

using namespace std;

const long long mod = 998244353;

struct matrix {
    static const int N = 5;
    long long a[N][N] = {}, n = 0, m = 0;
    matrix(int _n, int _m) : n(_n), m(_m) {}
    long long* operator[](const int &x) { return a[x]; }
};

matrix operator*(matrix A, matrix B) {
    int n = A.n, m = B.m, h = A.m;
    matrix ret(n, m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < h; k++)
                ret[i][j] = (ret[i][j] + A[i][k] * B[k][j]) % mod;
    return ret;
}

matrix ksm(matrix A, long long b) {
    matrix ret(A.n, A.m);
    for (int i = 0; i < A.n; i++) ret[i][i] = 1;
    while (b) {
        if (b&1) ret = ret * A;
        A = A * A;
        b >>= 1;
    }
    return ret;
}

void solve() {
    long long a1, a2, a3, x, y, n;
    cin >> a1 >> a2 >> x >> y >> n;
    matrix T(5, 5), v(5, 1);
    T[0][0] = x*x % mod, T[0][1] = T[0][2] = x*y % mod, T[0][3] = y*y % mod;
    T[1][0] = T[2][0] = x, T[1][2] = T[2][1] = y;
    T[3][0] = T[4][0] = T[4][4] = 1;
    a3 = (x*a2 + y*a1) % mod;
    v[0][0] = a3*a2 % mod, v[1][0] = a3*a1 % mod;
    v[2][0] = a2*a2 % mod, v[3][0] = a2*a1 % mod;
    v[4][0] = a1*a2 % mod;
    cout << (ksm(T, n-2) * v)[4][0] << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

:::