2024.7 做题 & 补题

Nygglatho · 2024-09-04 10:26:08 · 个人记录

sxyz 做题记录？

7.8.

图论讲课.

还需要学下 Johnson 和 Boruvka.

P6381

不会总结题面。
对边权分解质因数。由于 a^kb^k=(ab)^k，所以把已经有 k 次方的都消掉，即 e \to a_1^{b_1} \times a_2^{b_2} \times \cdots \to a_1^{b_1\bmod k}\times a_2^{b_2 \bmod k}\times \cdots。容易发现这样不影响答案。
容易发现，对于 i,j，满足条件当且仅当相乘次方数量为 k。
对于修改后的 e，令 \theta = a_1^{k-b_1\bmod k}\times a_2^{k-b_2 \bmod k}\times \cdots。
则对于 (u,v) 满足条件，当且仅当 e_u=\theta_v。
存到一个 map 里，进行 DAG 上 DP 即可。


void Topo() {
F(i, 1, n)
    if (ind[i] == 0) q.push(i);

while (!q.empty()) {
    int u = q.front(); q.pop();

    for (int i = hd[u]; i; i = e[i].nxt) {
        int v = e[i].to;

        mp[v][e[i].w] = max(mp[v][e[i].w], mp[u][e[i]._w] + e[i].l);
        ans = max(ans, mp[v][e[i].w]);
        -- ind[v];

        if (ind[v] == 0) q.push(v);
    }
}
}

int main() { cin >> n >> m >> k;

F(i, 1, m) {
    int u, v; ll w, l;

    cin >> u >> v >> w >> l;

    ll _ = w, _w = 1ll, __ = 1ll;

    for (ll i = 2; i * i <= _; ++ i) {
        int tot = 0;

        while (_ % i == 0ll) {++ tot, _ /= i;}
        F(j, 1, (tot % k)) _w *= i;
        if (tot % k != 0) F(j, 1, k - (tot % k)) __ *= i;
    }

    if (k - 1) _w *= _;

    F(i, 1, k - 1) __ *= _;
    addedge(u, v, _w, __, l);

    ++ ind[v];
}

Topo();

cout << ans;

}

CF1473E
- 题面很简洁了。
- 令 1\sim n 节点为未进行 -\max 和 +\min 操作的。
- 显然如果减少，-\max 一定最优，增加 \min 同样一定最优。
- 因此对于 (u,v)：
- 跑一下 Dijkstra 即可。
CF1442C
- 题面很简洁了。
P8867

7.9

咕

7.10.

模拟赛。唐完了

P4349
- 有一个 N 位的数字，将其分割，以保证每个区间里的数字可以被 M 整除。
- 模拟赛加了分割位数 \in [L,R] 的限制。
- 注意到，1 \sim i 区间内的数可以划分以被 M 整除 当且仅当 1 \sim i 组成的数能被 M 整除。
- 证明：假设 1 \sim i 不能被整除，且可以被划分为 [1,\omega_1],[\omega_1+1,\omega_2],\cdots,[\omega_k+1,i]。
- 当 k=1 时：
  - 如果 \omega+1 \sim i 不能被整除，显然不能分。
  - 如果 \omega+1 \sim i 能被整除，令 \omega+1\sim i 组成的数为 s_2，1\sim\omega 组成 s_1，1\sim i 组成 s，则 s=s_1\times 10^{i-\omega}+s_2。
  - 由于 s_2 \bmod M =0，s\bmod M\ne0，如果 s_1\bmod M=0，则 s\bmod M=(s_1\times 10^{i-\omega})\bmod M+s_2\bmod M=((s_1 \bmod M)\times10^{i-w}\bmod M)\bmod M+s_2\bmod M=0+0=0。
  - 与题意不符。
  - 否则，s_1 \bmod M \ne 0，显然不能分，与题意不符。
- 当 k>1 时，同理，可以转化为 k-1,\cdots,1 的情况。
- 做 DP 算方案数量即可。
- 可以双指针扫或者用 Seg 维护。
- ```
int main() {
IOS
cin >> n >> m/* >> l >> r*/;
l = 1, r = n;
cin >> st ;
st = ' ' + st;
F(i, 1, n) a[i] = st[i] - '0';
F(i, 1, n) _[i] = (_[i - 1] * 10ll + a[i]) % m;
ll sum = 0ll;
int L = 1 - r, R = 1 - l;
for (int i = 1; i <= n; ++ i) {
    if (_[i] % m == 0) {
        if (i >= l && i <= r) f[i] = 1ll;
        f[i] += sum ;
        f[i] %= mod ;
    }
    if (R >= 0) sum += f[R + 1]; sum %= mod; 
    if (L > 0) sum += mod - f[L]; sum %= mod;
    ++ L, ++ R;
}
cout << f[n];
}
```
P9820
- 唐题，但忘打 freopen。
咕

7.11.

启发式搜索和估价函数。

7.12.

7.13.

唐.薯薯题没想到，喜提 50 \text{pts}

AGC025B

还。是。写。下。吧。
有 n 个格子排成一排，每个格子可以涂成红、蓝、绿或不涂色，得分分别为 A,B,A+B,0。求使总得分为 K 的方案数，答案对 998244353 取模
赛时加强到任意质数模数，需要用 Lucas 定理/fn
设红色有 x 个，绿色有 y 个，没有紫色，则有 Ax+By=k。
由于 n \le 3 \times 10^5，所以不用 exgcd。
然后开始想歪了。
令紫色为 i 个，则答案为
s = \sum\limits_{i=0}^{\min(x,y)}\binom{n}{x-i}\cdot \binom{n-x+i}{y-i}\cdot \binom{n-x-y+2i}{i}
然后赛场上对着这个化简了 3 小时，没化简出来/fad
最坏时间复杂度 O(n \min(n,k))。
正解：把它看成 n 列 2 行的方格，第一行为红，第二行为蓝，如果红和蓝在一个格子就是紫色。
公式简单的
关于 Lucas：
\binom{n}{k} \bmod p = \binom{n \bmod p}{k \bmod p} \cdot \binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{k}{p}\rfloor} \bmod p
```
struct Shiroko {
ll x, y;
};
```

vector <Shiroko> v;

//ll mod;

namespace Maths {

ll f[1200000];

inline void Init() {
    f[0] = 1ll;

    F(i, 1, 1199999) f[i] = f[i - 1] * (1ll * i) % mod;
}

inline ll qp(ll x, ll y) {
    if (y == 0ll) return 1ll;

    ll Chtholly = qp(x, y / 2ll);

    if (y & 1ll) return Chtholly * Chtholly % mod * x % mod;
    else return Chtholly * Chtholly % mod;
}

inline ll div(ll x) {
    return qp(x, mod - 2ll) % mod;
}

inline ll C(ll n, ll m) {
    if (m > n) return 0ll;
    return f[n] * div(f[m]) % mod * div(f[n - m]) % mod;
}

inline ll Lucas (ll n, ll m) {
    if (m > n) return 0ll;
    if (m == 0ll) return 1ll;

    return C(n % mod, m % mod) * Lucas(n / mod, m / mod) % mod;
}

} ll ans = 0ll; int main() { // OPEN cin >> n >> A >> B >> K >> mod;

Maths::Init();

if (A == 0 && B == 0) {
    if (K == 0) {
        cout << Maths::qp(4ll, n);
        return 0;
    } else {
        cout << 0;
        return 0;
    }
}
if (B == 0) {
    if (K % A != 0) {
        cout << 0;
        return 0;
    }
    ll _ = K / A;
    if (K / A > n) {cout << 0; return 0;}
    cout << Maths::Lucas(n, _) * Maths::qp(2, _) % mod * Maths::qp(2, n - _) % mod;
    return 0;
}
if (A == 0) {
    if (K % B != 0) {
        cout << 0;
        return 0;
    }
    ll _ = K / B;
    if (K / B > n) {cout << 0; return 0;}
    cout << Maths::Lucas(n, _) * Maths::qp(2, _) % mod * Maths::qp(2, n - _) % mod;
    return 0;
}

for (ll i = 0ll; i <= n; ++ i) {
    ll _ = K - A * i;

    if (_ % B == 0) {
        ll y = _ / B;
        if (y <= n && y >= 0) v.push_back({i, y});
    }
}

for (Shiroko i : v) {
    ans += Maths::Lucas(n, i.y) * Maths::Lucas(n, i.x); ans %= mod;
}
cout << ans;

}

7.16

T1 唐题，期望得分 100，实际得分 20/fn
T2 比 T3 难.jpeg
T3 神秘随机题，期望得分 [50,100]，实际得分 100
- 大意：有一个长度为 n 的序列 a，他需要从中选出一个元素个数为 k(k\ge\left\lceil\dfrac{n}{2}\right\rceil) 的子序列 w，使得 \gcd\limits_{i=1}^k w_i 最大。
- 正解是 O(\max d(a_i)^2) 的，但是我 O(\max d(a_i)\cdot n) 加去重居然能艹过/fad
- 拜谢喵喵 O(\max d(a_i)\cdot \max \omega(a_i)) 神仙高维后缀和做法/bx
- 随机取一个 p。
- 找出 p 的因数，对所有 a_i 判断这是不是公因数，如果有 \ge\left\lceil\dfrac{n}{2}\right\rceil 个，则更新答案。
- 因为 p 有 至少 \dfrac{1}{2} 的概率是 w 中的，随机 15 次，每次询问就有不到 \dfrac{1}{2^{15}} 的概率出错，比 U Rock 掉 U Moon 概率还低。
- 代码跟屎一样
- ```
mt19937 rng(time(0));
```
ll a[100010]; ll f[100010];

int r[18];

void w(int x) { for (ll i = 1ll; i i <= a[x]; ++ i) if (a[x] % i == 0ll) { if (i i == a[x]) f[++ m] = i; else {f[++ m] = i; f[++ m] = a[x] / i;} } }

bool cmp(ll x, ll y) {return x > y;}

int main() { OPEN int T; IOS
```
cin >> T;

while (T --) {

    cin >> n;

    F(i, 1, n) cin >> a[i];

    F(i, 1, 14) r[i] = rng() % n + 1;

    F(i, 1, 14) w(r[i]);

    sort (f + 1, f + m + 1, cmp);
    m = unique(f + 1, f + m + 1) - f - 1;
    F(i, 1, m) {
        int tot = 0;
        F(j, 1, n) {
            if (a[j] % f[i] == 0) ++ tot;
        }
        if (tot * 2 >= n) {
            cout << f[i] << '\n';
            break ;
        }
    }
}
return 0;
```
}

7.17.

基础数据结构.

都是典题。

CF865D
- 已知接下来 N 天的股票价格，每天你可以买进一股股票，卖出一股股票，或者什么也不做。N 天之后你拥有的股票应为 0，求这 N 天内能够赚最多的钱数。
- 反悔贪心典。
- 注意到，不做等价于买进然后原价卖出。
- 所以碰到一个数，可以直接买进，因为即使之后亏损也会在最后原价卖出。
- 如果碰到一个数大于最小，就直接卖出最小价值的。
- 注意到此时如果再买进当前的，等价于不做，但是还有一种选择是不卖出最小，买进当前的。
- 可以用堆维护。
- ```
F(i, 1, n) {
ll x;
cin >> x;
if (q.empty()) {
    q.push(x);
    continue ;
}
ll w = q.top();
if (w < x) {
    ans += (x - w);
    q.pop(); q.push(x); q.push(x);
} else {
    q.push(x);
}
}
```

CF883J

有 m 个建筑，每个建筑拆除需要 p_i 代价，装修需要 b_i 代价。有 n 个月，每个月预算 a_i。每个月可以拆除若干建筑，但对于第 i 天，建筑 j 需要 b_j \le a_i 才能拆除。
拆除可以用到之前存的预算，求最多拆除多少个建筑。
发现把钱留到尽可能后面一定不劣。
但是还有 b_j \le a_i 的限制。
先把 b_j \le a_i 且 \forall \omega \in [i + 1, n], a_{\omega} < b_j 的尽量在 a_i 拆掉。
之后就是反悔贪心板子了。

int main() {
IOS

cin >> n >> m;

F(i, 1, n) cin >> s[i];
F(i, 1, m) cin >> f[i].b;
F(i, 1, m) cin >> f[i].p;

sort(f + 1, f + m + 1, cmp);
D(i, n, 1) {
    if (s[i] > mx[i + 1]) tag[i] = 1;
    mx[i] = max(mx[i + 1], s[i]);
}

for (int i = 1, j = 1; i <= n; ++ i) {
    sum += s[i];
    if (! tag[i]) continue;

    while (j <= m) {
        if (f[j].b > s[i]) {++ j; continue ;}
        if (f[j].b <= mx[i + 1]) break ;
        if (f[j].p > sum && q.empty()) {++ j; continue ;}

        if (f[j].p > sum && q.top() < f[j]) {++ j; continue ;}

        if (f[j].p > sum) {
            sum -= f[j].p;
            sum += q.top().p;
            q.pop();
            q.push(f[j]);
        } else {
            sum -= f[j].p;
            q.push(f[j]);
            ++ tot;
        }
        ++ j;

    }
}
cout << tot;
}

ABC359E

Seg & Fenwick (7.18)

CF558E

题目大意：给定一个长度不超过 10^5 的字符串（小写英文字母），和不超过 50000 个操作。

每个操作 \texttt{L\ R\ K} 表示给区间 [L,R] 的字符串排序，K=1 为升序，K=0 为降序。

小写英文字母，值域不超过 26！
对于 \tt a 到 \tt z，开一个线段树维护数量。
然后直接用技术排序的思想区间覆盖就行了。


bool st;
string str;
struct Node {
int tag;

int w[27];

Node operator +(const Node& p) const {
    Node q; q.tag = 0;
    q.w[0] = 0;
    F(i, 1, 26) q.w[i] = p.w[i] + w[i];
    return q;
}

}f[410000];

bool ed;

void Build(int l, int r, int p) { if (l == r) { int v = str[l] - 97 + 1;

    F(i, 1, 26)
        if (i != v) f[p].w[i] = 0;
        else f[p].w[i] = 1;
    return ;
}
int m = (l + r) / 2;
Build (l, m, ls(p));
Build (m + 1, r, rs(p));
f[p] = f[ls(p)] + f[rs(p)];

}

void pushdown(int l, int r, int p) { if (f[p].tag == 0) return ;

int m = (l + r) / 2;
int v = f[p].tag;
F(i, 1, 26) {
    if (i != v) f[ls(p)].w[i] = 0;
    else f[ls(p)].w[i] = (m - l + 1);
    if (i != v) f[rs(p)].w[i] = 0;
    else f[rs(p)].w[i] = (r - m);
}
f[ls(p)].tag = f[rs(p)].tag = f[p].tag;
f[p].tag = 0;

}

void cover(int l, int r, int s, int t, int p, int v) { if (l <= s && t <= r) { F(i, 1, 26) if (i != v) f[p].w[i] = 0; else f[p].w[i] = (t - s + 1); f[p].tag = v; return; }

int m = (s + t) / 2;

pushdown(s, t, p);

if (l <= m) cover(l, r, s, m, ls(p), v);
if (m < r) cover (l, r, m + 1, t, rs(p), v);

f[p] = f[ls(p)] + f[rs(p)];

}

char query(int l, int r, int x, int p) { if (l == r) { F(i, 1, 26) if (f[p].w[i] >= 1) return char(i + 96); return '?'; }

pushdown(l, r, p);

int m = (l + r) / 2;
if (x <= m) return query(l, m, x, ls(p));
else return query(m + 1, r, x, rs(p));

}

Node querycnt(int l, int r, int s, int t, int p) { if (l <= s && t <= r) { return f[p]; }

pushdown(s, t, p);

int m =(s + t) / 2;
Node w;
if (l <= m && m < r) w = querycnt(l, r, s, m, ls(p)) + querycnt(l, r, m + 1, t, rs(p));
else if (l <= m) w = querycnt(l, r, s, m, ls(p));
else if (m < r) w = querycnt(l, r, m + 1, t, rs(p));

return w;

}

void upsort(int l, int r) { Node _ = querycnt(l, r, 1, n, 1);

for (int i = 1, j = l; i <= 26; ++ i) {
    if (_.w[i] == 0) continue ;

    cover(j, j + _.w[i] - 1, 1, n, 1, i);

    j += _.w[i];
}

}

void downsort(int l, int r) { Node = querycnt(l, r, 1, n, 1); for (int i = 26, j = l; i >= 1; -- i) { if (.w[i] == 0) continue ;

    cover(j, j + _.w[i] - 1, 1, n, 1, i);

    j += _.w[i];
}

}

P2572
- 。
- 区间最长连续，最大子段和这种 trick 很常见了。
- 维护最长连续 0 个数，最长连续 1 个数
- 和左端右端最长连续。
- 然后打 3 种 \text{tag}。
- 区间取反
- 区间变 0
- 区间变 1
- 取反下传的时候，如果有标记了，就把标记取反。
- 如区间变 0 变成区间变 1。
- ```
struct Node {
ll cnt0, cnt1;

ll mx0, mx1;

ll mxl0, mxl1;
ll mxr0, mxr1;

Node operator +(const Node& p) const {
    Node q;
    q.cnt0 = cnt0 + p.cnt0;
    q.cnt1 = cnt1 + p.cnt1;
    if (cnt1 == 0) q.mxl0 = mxl0 + p.mxl0;
    else q.mxl0 = mxl0;
    if (cnt0 == 0) q.mxl1 = mxl1 + p.mxl1;
    else q.mxl1 = mxl1;
    if (p.cnt1 == 0) q.mxr0 = p.mxr0 + mxr0;
    else q.mxr0 = p.mxr0;
    if (p.cnt0 == 0) q.mxr1 = p.mxr1 + mxr1;
    else q.mxr1 = p.mxr1;

    q.mx0 = max(mx0, max(p.mx0, mxr0 + p.mxl0));
    q.mx1 = max(mx1, max(p.mx1, mxr1 + p.mxl1));

    return q;
}
```
}S[420000]; int a[110000]; int tag[410000]; bool ed;

void Build (int l, int r, int p) { if (l == r) { if (a[l] == 0) { S[p].cnt0 = S[p].mxl0 = S[p].mxr0 = S[p].mx0 = 1; S[p].cnt1 = S[p].mxl1 = S[p].mxr1 = S[p].mx1 = 0; } else { S[p].cnt0 = S[p].mxl0 = S[p].mxr0 = S[p].mx0 = 0; S[p].cnt1 = S[p].mxl1 = S[p].mxr1 = S[p].mx1 = 1; } return ; }
```
int m = (l + r) / 2;

Build (l, m, ls(p));
Build (m + 1, r, rs(p));

S[p] = S[ls(p)] + S[rs(p)];
```
}

void pushdown(int l, int r, int p) { if (tag[p] == 0) { int m = (l + r) / 2; S[ls(p)].cnt0 = S[ls(p)].mxl0 = S[ls(p)].mxr0 = S[ls(p)].mx0 = m - l + 1; S[ls(p)].cnt1 = S[ls(p)].mxl1 = S[ls(p)].mxr1 = S[ls(p)].mx1 = 0; tag[ls(p)] = 0; S[rs(p)].cnt0 = S[rs(p)].mxl0 = S[rs(p)].mxr0 = S[rs(p)].mx0 = r - m; S[rs(p)].cnt1 = S[rs(p)].mxl1 = S[rs(p)].mxr1 = S[rs(p)].mx1 = 0; tag[rs(p)] = 0; } else if (tag[p] == 1) { int m = (l + r) / 2; S[ls(p)].cnt0 = S[ls(p)].mxl0 = S[ls(p)].mxr0 = S[ls(p)].mx0 = 0; S[ls(p)].cnt1 = S[ls(p)].mxl1 = S[ls(p)].mxr1 = S[ls(p)].mx1 = m - l + 1; tag[ls(p)] = 1; S[rs(p)].cnt0 = S[rs(p)].mxl0 = S[rs(p)].mxr0 = S[rs(p)].mx0 = 0; S[rs(p)].cnt1 = S[rs(p)].mxl1 = S[rs(p)].mxr1 = S[rs(p)].mx1 = r - m; tag[rs(p)] = 1; } else if (tag[p] == 2) { int m = (l + r) / 2; swap(S[ls(p)].cnt0, S[ls(p)].cnt1); swap(S[ls(p)].mx0, S[ls(p)].mx1); swap(S[ls(p)].mxl0, S[ls(p)].mxl1); swap(S[ls(p)].mxr0, S[ls(p)].mxr1); if (tag[ls(p)] == -1) tag[ls(p)] = 2; else tag[ls(p)] ^= 1;
```
    swap(S[rs(p)].cnt0, S[rs(p)].cnt1);
    swap(S[rs(p)].mx0, S[rs(p)].mx1);
    swap(S[rs(p)].mxl0, S[rs(p)].mxl1);
    swap(S[rs(p)].mxr0, S[rs(p)].mxr1);
    if (tag[rs(p)] == -1) tag[rs(p)] = 2;
    else tag[rs(p)] ^= 1;
}
tag[p] = -1;
```
}

void upd0(int l, int r, int s, int t, int p) { if (l <= s && t <= r) { S[p].cnt0 = S[p].mxl0 = S[p].mxr0 = S[p].mx0 = t - s + 1; S[p].cnt1 = S[p].mxl1 = S[p].mxr1 = S[p].mx1 = 0; tag[p] = 0; return ; } if (tag[p] != -1) pushdown(s, t, p);
```
int m = (s + t) / 2;

if (l <= m)upd0(l, r, s, m, ls(p));
if (m < r) upd0(l, r, m + 1, t, rs(p));
S[p] = S[ls(p)] + S[rs(p)];
```
}

void upd1(int l, int r, int s, int t, int p) { if (l <= s && t <= r) { S[p].cnt0 = S[p].mxl0 = S[p].mxr0 = S[p].mx0 = 0; S[p].cnt1 = S[p].mxl1 = S[p].mxr1 = S[p].mx1 = t - s + 1; tag[p] = 1; return ; } pushdown(s, t, p);
```
int m = (s + t) / 2;

if (l <= m)upd1(l, r, s, m, ls(p));
if (m < r) upd1(l, r, m + 1, t, rs(p));
S[p] = S[ls(p)] + S[rs(p)];
```
}

void upd2(int l, int r, int s, int t, int p) { if (l <= s && t <= r) { swap(S[p].cnt0, S[p].cnt1); swap(S[p].mx0, S[p].mx1); swap(S[p].mxl0, S[p].mxl1); swap(S[p].mxr0, S[p].mxr1); if (tag[p] == -1) tag[p] = 2; else tag[p] ^= 1; return ; } pushdown(s, t, p); int m = (s + t) / 2; if (l <= m) upd2(l, r, s, m, ls(p)); if (m < r) upd2(l, r, m + 1, t, rs(p)); S[p] = S[ls(p)] + S[rs(p)]; }

Node newnode() { Node t; t.cnt0 = t.cnt1 = t.mx0 = t.mx1 = t.mxl0 = t.mxl1 = t.mxr0 = t.mxr1 = 0; return t; }

Node query(int l, int r, int s, int t, int p) { if (l <= s && t <= r) { return S[p]; } Node w = newnode(); pushdown(s, t, p); int m = (s + t) / 2; if (l <= m && m < r) w = query(l, r, s, m, ls(p)) + query(l, r, m + 1, t, rs(p)); else if (l <= m) w = query(l, r, s, m, ls(p)); else if (m < r) w = query(l, r, m + 1, t, rs(p)); return w; }

7.19

P9196
- 建立两个 Trie，存储 S_i 的前缀和后缀。
- 对每一个 S_i，找到她从前往后的 \text{dfn} 值和从后往前的 \text{dfn} 值，记为 x_i, y_i。
- 容易发现，前缀相同，在 Trie 里的 \text{dfn} 值是连续的。
- 预处理每一个前缀所对应的 \text{dfn} 区间和后缀的 \text{dfn} 区间，记为 [L,R]，[X,Y]。
- 则答案变为满足 L \le x_i \le R,X\le y_i\le Y 的点数量。
- 板子题。
- 按 x_i 排序。
- 遍历 x_i，将 y_i 的值加入到数组中。
- 如果扫到了 L，记录 \le L 且在 [X,Y] 区间内的点数量 \text{sum}_1。
- 如果扫到了 R，记录 \le R 且在 [X,Y] 区间内的点数量 \text{sum}_2。
- 单点修改，区间查询，用 Seg 维护。注意顺序是先记录 \text{sum}_1，再将纵坐标 y_i 的数量 +1，最后统计 \text{sum}_2。
- 6.3KB 应当代码

7.25

一道递推题：
- 给定 n，构造 1 \sim n 排列 p，要求 \forall 1\le i\le n,p_i\ne i，求方案数。
- 令 d_x 表示 n=x 时方案。则有 d_x=(x-1)(d_{x-1}+d_{x-2})。
- 证明：令 p_x=\theta(1\le\theta<x)。
- 由于有两种可能：
- - 两个固定了，其余 $x-2$ 未固定，为 $d_{x-2}$。
- - 同理，$d_{x-1}$。