AtCoder Beginner Contest 215

比赛链接

D Coprime 2

Description

题目链接

Solution

先预处理哪些质因数出现过，那么满足条件的数不能含有这些质因数。

Code

Coprime 2

#include <bits/stdc++.h>

using namespace std;

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 1e5 + 5, MOD = 1e9 + 7;

int n, m, vis[MAXN];
vector<int> divs[MAXN];

int main() {
    boost;
    cin >> n >> m;
    for (int i = 1; i < MAXN; i++)
        for (int j = i; j < MAXN; j += i)
            divs[j].push_back(i);
    for (int i = 1, tmp; i <= n; i++) {
        cin >> tmp;
        for (auto& j : divs[tmp]) vis[j] = true;
    }
    vis[1] = 0;
    vector<int> ans;
    for (int i = 1; i <= m; i++) {
        bool ok = true;
        for (auto& j : divs[i]) if (vis[j]) ok = false;
        if (ok) ans.push_back(i);
    }
    cout << ans.size() << "\n";
    for (auto& i : ans) cout << i << "\n";
    return 0;
}

E Chain Contestant

Description

题目链接

Solution

设 $dp[i][j][k]$ 表示考虑到第 $i$ 个字符，已选择的字符集为 $j(j \neq \empty)$，最后一个选取的字符为 $k$ 的方案数。

考虑第 $i+1$ 个字符 $k'$：

1. 加入字符 $k'$

   • 若 $k' \in j$，必有 $k'=k$，从而有 $dp[i+1][j][k'] \leftarrow dp[i][j][k]$。
   • 若 $k' \notin j$，有 $dp[i+1][j∪k'][k'] \leftarrow dp[i][j][k]$。
   • 若 $k'$ 是第一个加入的字符，有 $dp[i+1][k'][k'] \leftarrow 1$。

2. 不加入字符 $k'$

   • 字符集和最后加入的字符都没有改变，有 $dp[i+1][j][k] \leftarrow dp[i][j][k]$。

Code

Chain Contestant

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 1025;
const int MOD = 998244353;
int n, a[MAXN];
int dp[2][MAXN][10];

void add(int& a, int b) { a = (a + b) % MOD; }

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        a[i] = c - 'A';
    }
    // 10 为空
    for (int i = 1; i <= n; i++) {
        memset(dp[i & 1], 0, sizeof(dp[i & 1]));
        // 空串
        add(dp[i & 1][1 << a[i]][a[i]], 1);
        // 非空串
        for (int s = 1; s < (1 << 10); s++) {
            if ((s >> a[i]) & 1) {
                // 选 a[i]
                add(dp[i & 1][s][a[i]], dp[(i & 1) ^ 1][s][a[i]]);
                // 不选 a[i]
                for (int k = 0; k <= 9; k++)
                    if ((s >> k) & 1)
                        add(dp[i & 1][s][k], dp[(i & 1) ^ 1][s][k]);
            } else {
                // 选 a[i]
                for (int k = 0; k <= 9; k++) {
                    if ((s >> k) & 1)
                        add(dp[i & 1][s | (1 << a[i])][a[i]],
                            dp[(i & 1) ^ 1][s][k]);
                }
                // 不选 a[i]
                for (int k = 0; k <= 9; k++) {
                    if ((s >> k) & 1)
                        add(dp[i & 1][s][k], dp[(i & 1) ^ 1][s][k]);
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < (1 << 10); i++)
        for (int k = 0; k < 10; k++)
            if ((i >> k) & 1) add(ans, dp[n & 1][i][k]);
    cout << ans;
    return 0;
}

F Dist Max 2

Description

题目链接

Solution

将点按横坐标排序，二分最大距离 $d$，接下验证最大距离能否至少是 $d$。对于点 $i$，满足和它距离至少是 $d$ 的点的横坐标一定小于等于 $x_i-d$，设这些点在区间 $[1,k]$ 中，$k$ 可以用 lower_bound 快速求得。在这些点中，必须存在一个点 $j$，满足 $|y_j-y_i| \ge d$。我们不必考察区间内每一个点的纵坐标，而只需要考察区间内 $y$ 的最大值和最小值，这里区间最值可用线段树快速求解（也可以利用单调队列）。

时间复杂度：$O(NlogNlog\max \limits_{1 \le i \le N}(x_i,y_i))$ 或 $O(Nlog\max \limits_{1 \le i \le N}(x_i,y_i))$，取决于区间最值的求解方式。

Code

Dist Max 2

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int n, m, T;

#define lid id << 1
#define rid id << 1 | 1

vector<pair<int, int>> p;

struct node {
    int l, r;
    int mx, mi;
} tr[MAXN << 2];

void update(int id) {
    tr[id].mx = max(tr[lid].mx, tr[rid].mx);
    tr[id].mi = min(tr[lid].mi, tr[rid].mi);
}

void build(int id, int l, int r) {
    tr[id].l = l, tr[id].r = r;
    if (l == r) {
        tr[id].mx = p[l].second;
        tr[id].mi = p[l].second;
        return;
    }
    int mid = l + r >> 1;
    build(lid, l, mid);
    build(rid, mid + 1, r);
    update(id);
}

int qmin(int id, int l, int r) {
    if (tr[id].l == l && tr[id].r == r) return tr[id].mi;
    int mid = tr[id].l + tr[id].r >> 1;
    if (r <= mid)
        return qmin(lid, l, r);
    else if (l > mid)
        return qmin(rid, l, r);
    else
        return min(qmin(lid, l, mid), qmin(rid, mid + 1, r));
}

int qmax(int id, int l, int r) {
    if (tr[id].l == l && tr[id].r == r) return tr[id].mx;
    int mid = tr[id].l + tr[id].r >> 1;
    if (r <= mid)
        return qmax(lid, l, r);
    else if (l > mid)
        return qmax(rid, l, r);
    else
        return max(qmax(lid, l, mid), qmax(rid, mid + 1, r));
}

bool check(int mid) {
    for (int i = 1; i <= n; i++) {
        int id1 = lower_bound(p.begin() + 1, p.end(),
                              make_pair(p[i].first + mid, 0)) -
                  p.begin();
        int id2 = upper_bound(p.begin() + 1, p.end(),
                              make_pair(p[i].first - mid, 0)) -
                  p.begin() - 1;
        bool tag = 0;
        if (id1 <= n) {
            if (qmax(1, id1, n) - p[i].second >= mid ||
                p[i].second - qmin(1, id1, n) >= mid)
                tag = 1;
            else
                tag = 0;
        }
        if (id2 >= 1) {
            if (qmax(1, 1, id2) - p[i].second >= mid ||
                p[i].second - qmin(1, 1, id2) >= mid)
                tag = 1;
            else
                tag = 0;
        }
        if (tag) return true;
    }
    return false;
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    p.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> p[i].first >> p[i].second;
    sort(p.begin() + 1, p.end());
    build(1, 1, n);
    int l = 0, r = 1e9, ans;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else
            r = mid - 1;
    }
    cout << ans;
    return 0;
}

G Colorful Candies 2

Description

题目链接

Solution

设总共有 $C$ 种不同的颜色，定义随机变量 $X_i$ 表示是否有颜色 $i$，$m_i$ 表示第 $i$ 种颜色出现次数，则对于给定的 $K$，答案为 $\sum\limits_{i=1}^{C} EX_i= \sum\limits_{i=1}^{C} \frac{\binom{N}{K}-\binom{N-m_i}{K}}{\binom{N}{K}}$。直接求解的话时间复杂度为 $O(NC)$ 无法通过。

注意到 $\frac{\binom{N}{K}-\binom{N-m_i}{K}}{\binom{N}{K}}$ 在 $m$ 相同时的值是一样的，设 $f(m)$ 表示出现 $m$ 次的颜色有多少种，设不同的 $m$ 有 $M$ 个，分别为 $g_1,g_2,\dots,g_M$，那么答案又可以写成 $\sum\limits_{i=1}^{M}\frac{\binom{N}{K}-\binom{N-g_i}{K}}{\binom{N}{K}}*f(g_i)$。由 $N = g_1*f(g_1) + g_2*f(g_2) + \dots + g_M*f(g_M) \ge 1*f(1)+2*f(2)+\dots+M*f(M) \ge 1+2+\dots+M$ 可知 $M$ 不超过 $\sqrt{N}$，因此可在 $O(\sqrt{N})$ 时间内完成单次求解，从而总的时间复杂度为 $O(N\sqrt{N})$。

Code

Colorful Candies 2

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 5E4 + 5;
const int MOD = 998244353;
int n;
unordered_map<int, int> cntc, cntm;
LL fac[MAXN], inv[MAXN];

LL qpow(LL a, LL b, LL MOD) {
    LL ans = 1, base = a % MOD;
    while (b) {
        if (b & 1) ans = ans * base % MOD;
        b >>= 1, base = base * base % MOD;
    }
    return ans;
}

LL C(LL n, LL m) {
    if (m > n) return 0;
    return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= n; i++) {
        int c;
        cin >> c;
        cntc[c]++;
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = qpow(fac[i], MOD - 2, MOD);
    }
    for (auto& pii : cntc) cntm[pii.second]++;
    for (int k = 1; k <= n; k++) {
        LL ans = 0;
        LL v1 = C(n, k);
        LL inv1 = qpow(v1, MOD - 2, MOD);
        for (auto& pii : cntm) {
            ans += (v1 - C(n - pii.first, k)) * pii.second % MOD * inv1 % MOD;
            ans %= MOD;
        }
        cout << (ans + MOD) % MOD << endl;
    }
    return 0;
}