AtCoder Regular Contest 215 C-D 题解

AtCoder Regular Contest 215

C - Strong Surname

Question

Strong Surname

给定 $n$ 个三元组 $(x_i,y_i,z_i)$，你需要进行 $n-1$ 词操作，每次操作选择两个三元组 $(x_i,y_i,z_i),(x_j,y_j,z_j)$ 如果 $x_i\ge x_j\vee y_i\ge y_j\vee z_i\ge z_j$ 都满足则保留 $i$,否则任意保留一个并弃置另一个，求有多少个三元组可能成为最后剩下的三元组。

• $n\le 2\times {10}^5$
• $1\le x,y,z\le 2\times {10}^5$

Solution

考虑图论建模，对于两个人 $i,j$ 如果 $x_i\ge x_j\vee y_i\ge y_j\vee z_i\ge z_j$ ，那么我们可以建一条单向边 $i\to j$

发现边数最多可能达到 $n^2$，对这个图 SCC 缩点之后找入度为 0 的点就是答案

考虑前后缀优化建图，对于每一维排序后单独建图，从大到小排序后，如果 $i$ 和 $i+1$ 在这一维度上相等，那么就建双向边，否则建 $i\to j$ 单向边

Code

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int id;
    int x, y, z;
};

void solve() {
    int n; cin >> n;
    vector<Node> a(n);
    for (int i = 0; i < n; i++) {
        a[i].id = i + 1;
        cin >> a[i].x >> a[i].y >> a[i].z;
    }
    
    vector<vector<int>> g(n + 1);
    sort(a.begin(), a.end(), [](const Node &a, const Node &b) { return a.x > b.x; });

    for (int i = 0; i < n - 1; i++) {
        if (a[i].x == a[i + 1].x) {
            g[a[i + 1].id].push_back(a[i].id);
        }
        g[a[i].id].push_back(a[i + 1].id); 
    }

    sort(a.begin(), a.end(), [](const Node &a, const Node &b) { return a.y > b.y;});
    for (int i = 0; i < n - 1; i++) {
        if (a[i].y == a[i + 1].y) {
            g[a[i + 1].id].push_back(a[i].id);
        }
        g[a[i].id].push_back(a[i + 1].id);
    }

    sort(a.begin(), a.end(), [](const Node &a, const Node &b) { return a.z > b.z;});
    for (int i = 0; i < n - 1; i++) {
        if (a[i].z == a[i + 1].z) {
            g[a[i + 1].id].push_back(a[i].id);
        }
        g[a[i].id].push_back(a[i + 1].id); 
    }

    vector<int> dfn(n + 1, 0), low(n + 1, 0), scc(n + 1, 0);
    vector<bool> in_stack(n + 1, false);
    stack<int> stk;
    int cnt, scc_cnt;

    function<void(int)> tarjan = [&] (int u) {
        dfn[u] = low[u] = ++cnt;
        stk.push(u); in_stack[u] = true;
        for (int v : g[u]) {
            if (!dfn[v]) {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            }
            else if (in_stack[v]) low[u] = min(low[u], dfn[v]);
        }
        if (dfn[u] == low[u]) {
            scc_cnt++;
            while (true) {
                int x = stk.top(); stk.pop();
                in_stack[x] = false;
                scc[x] = scc_cnt;
                if (x == u) break;
            }
        }
    };

    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }

    vector<int> du(scc_cnt + 1, 0), cnt_scc(scc_cnt + 1, 0);
    for (int i = 1; i <= n; i++) {
        cnt_scc[scc[i]]++;
        for (int v : g[i]) {
            if (scc[i] != scc[v]) du[scc[v]]++;
        }
    }

    int ans = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        if (du[i] == 0) ans += cnt_scc[i];
    }

    cout << ans << "\n";
}

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

D - cresc

Question

由长度为 $N+1$ 的序列 $A$ 生成长度为 $N$ 的序列 $S$ 的方式如下：

• 对于每一个 $i$ ($1\le i\le N$), 满足 $S_i=A_i+A_{i+1}$.

求满足以下所有条件的长度为 $N$ 的序列 $S$ 的数量

• $S$ 非减

• 存在一个 $A$ 能构造出上述 $S$，$A$ 的每一个元素都在 $[1,M]$ 中

• $1\le N,M\le {10}^7$

Solution

由 $S_i\le S_{i+1}$ 得到 $A_i+A_{i+1}\le A_{i+1}+A_{i+2}$ 所以 $A_i\le A_{i+2}$

所以需要把 $A$ 分奇偶构造，得到 $A^{\prime }$ 和 $A^{″}$ 要求各自单调不降

考虑一个子问题：构造一个长度为 $x$ 的序列 $q$，取值范围为 $[0,y]$，单调不降的方案数

将 $q_i$ 一一映射到 $q_i^{\prime }=q_i+i-1$ 能保证严格单增，但取值范围变成 $[0,x+y-1]$，显然方案数为 $(\genfrac{}{}{0ex}{}{x+y-1}{x})$

但是这样会算重，不同的 A 序列可能会得到相同的 S 序列。

对于能构成相同 S 序列的 $A$ 序列集合，我们取其中一个 $[A_1,A_2,\cdots ]$，发现 $[A_1+k,A_2-k,A_3+k,\cdots ]$ 也在集合内，我们只统计集合中最大的 $k$

那么这样子必然满足两个条件其中的一个：

• $A_1=S_1,A_2=0$
• $A$ 奇数项序列 $A^{\prime }$ 的最后一个数为 $M$

由于是或的条件，用一个容斥统计即可

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

const int N = 3e7 + 5;

ll fac[N], inv[N];

ll fast_pow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % MOD;
    inv[N - 1] = fast_pow(fac[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
}

ll C(int n, int m) {
    if (n < m || m < 0) return 0;
    return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}

int main() {
    init();
    int n, m; cin >> n >> m;
    int odd = n / 2 + 1, even = n + 1 - odd;
    ll x1 = C(odd + m, m), x2 = C(even + m, m);
    ll y1 = C(odd + m - 1, m), y2 = C(even + m - 1, m);
    cout << ((x1 * y2 % MOD + x2 * y1 % MOD - y1 * y2 % MOD) % MOD + MOD) % MOD << '\n';
    return 0;
}