Niareh 的四月题解

__ryp__ · 2024-04-15 08:00:59 · 个人记录

A - 回忆

题意

在正整数集合中每次选取一对 x 与 y 使得 x - y \gt 0 \notin S，然后将其加入 S。计算最终 S 模的最大值。

分析

考虑到最终的 S 一定是一个等差数列，否则一定存在不属于 S 的非负 x - y。那么我们所要找的就是这个最终等差数列的公差。不难发现，其就是原序列的 \gcd。

因此，最终集合的模就是集合中最大的元素除以 \gcd。

复杂度： O(n\log n)

STD

#include <iostream>
using namespace std;

int gcd (int a, int b) { return b ? gcd (b, a % b) : a; }
int main (void)
{
    int n, res, v;

    ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
    cin >> n >> res, --n;
    while (n--) cin >> v, res = gcd (res, v);
    cout << v / res << '\n';
    return 0;
}

B - 街道

题意

给定一棵树，找其中距离小于等于 k 的点对的数量的总和。

分析

换根 DP 模板题。我们设 g(u, i) 代表在 u 子树中距离其小于等于 i 的点数量，有转移方程：

g(u, i) = \sum\limits_{v} g(v, i - 1)

然后，我们设 f(u, i) 表示在整棵树里距离 u 小于等于 i 的点数量，对于 u 的每个孩子 v ，有转移方程：

f(u, i) + g(v, i) - g(v, i - 2) & (i \ge 2) \\ g(v, 1) + 1 & (i = 1) \\ 1 & (i = 0) \end{cases}

不妨设点 1 为根，那么 f(1, i) = g(1, i)，转移即可。

复杂度： O(n)

STD

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int N = 2e5 + 10, K = 25;
ll f[N][K], g[N][K];
int k;
vector<int> e[N];

void dfs1 (int u, int fa)
{
    g[u][0] = 1;
    for (auto v : e[u])
        if (v != fa) {
            dfs1 (v, u);
            for (int i = 1; i <= k; i++) g[u][i] += g[v][i - 1];
        }
}

void dfs2 (int u, int fa)
{
    for (auto v : e[u]) 
        if (v != fa) {
            f[v][0] = 1, f[v][1] = g[v][1] + 1;
            for (int i = k; i >= 2; i--) f[v][i] = f[u][i - 1] + g[v][i] - g[v][i - 2];
        }
    for (auto v : e[u]) if (v != fa) dfs2 (v, u);
}

int main (void)
{
    int n;
    ll res = 0;

    ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        e[u].emplace_back (v), e[v].emplace_back (u);
    }

    dfs1 (1, 0);
    for (int i = 0; i <= k; i++) f[1][i] = g[1][i];
    dfs2 (1, 0);
    for (int i = 1; i <= n; i++) for (int j = 0; j <= k; j++) res += f[i][j];
    cout << res << '\n';
    return 0;
}

C - 数环

题意

从 n 个数中选出几个，使得其和在模 p 的意义下最大。

分析

注意数据范围 n \le 40。若暴搜 O(2^n) 显然无法通过。我们考虑折半搜索，即 meet-in-the-middle。

将序列均分成两半。对于左边，我们搜出所有和并存在数组中，并排序。对于右边，我们枚举能加出的每个和。考虑右边每个和能和左边哪些组合产生最大值。

设在右边搜出了 v，那么首先可以和左边第一个，即最大的使得 u \lt p - v 的结合。其次，我们可以和最大值结合，因为其与 v 的和模 p 后一定不劣于其他大于 p 的和。

复杂度： O(2^{n/2}\log n + n\log n)

STD

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 42;
int z[N], n, m, res = 0;
vector<int> w;

void dfs1 (int x, int sum)
{
    if (x > n / 2) return w.push_back (sum), void ();
    dfs1 (x + 1, sum), dfs1 (x + 1, (sum + z[x]) % m);
}

void dfs2 (int x, int sum)
{
    if (x > n) {
        int p = lower_bound (begin (w), end (w), m - sum)[-1];
        res = max (res, max (p + sum, (w.back () + sum) % m));
        return;
    }

    dfs2 (x + 1, sum), dfs2 (x + 1, (sum + z[x]) % m);
}

int main (void)
{
    ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> z[i];
    dfs1 (1, 0), sort (begin (w), end (w)), dfs2 (n / 2 + 1, 0);
    cout << res << '\n';
    return 0;
}

D - 周期

题意

给定一个 n 点 n 边的无向图（基环树），可以改变每条边的方向。若随机等概率改变，求不出现环的概率模 998244353。

分析

我们知道，一个有向环存在，当且仅当环上所有边的方向相同。那么，对每个无向环，只有两种情况能存在环。

可能存在多个环。我们设环总共的大小为 x，每个环的大小为 x_i，那么答案就是：

2^{-n} \times 2^{n-x} \times \prod\limits_{i} (2^{x_i}-2)

即

2^{-x} \times\prod\limits_{i}(2^{x_i}-2)

复杂度： O(n\log n)

STD

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int N = 2e5 + 10, P = 998244353;
vector<int> e[N];
int dep[N], w[N], nr = 0, tst = 0;

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

void dfs (int u, int fa)
{
    dep[u] = dep[fa] + 1;
    for (auto v : e[u])
        if (!dep[v]) dfs (v, u);
        else if (dep[v] > dep[u]) w[nr++] = dep[v] - dep[u] + 1;
}

int main (void)
{
    int n;
    ll cnt = 0, prd = 1;

    ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
    cin >> n;
    for (int u = 1, v; u <= n; u++) cin >> v, e[u].push_back (v), e[v].push_back (u);
    for (int u = 1; u <= n; u++) if (!dep[u]) dfs (u, 0);
    for (int i = 0; i < nr; i++) (cnt += w[i]) %= P, (prd *= (fxp (2, w[i]) + P - 2) % P) %= P;
    cout << fxp (fxp (2, cnt), P - 2) * prd % P << '\n';
    return 0;
}

F - 人偶

题意

从 n 个物品中不断选 P 次（P \rightarrow \infty），若超过 k 个就弹出队头。每个物品被选中的概率是 p_i，只能选中一次。求最终每个物品在队中的概率。

分析

最终队列不满的概率大概是 \prod (1-p)^P 量级的，早就爆掉精度了，不计。因此我们只计算队列满的情况下的概率。

可以直接状压。设 f(S) 是选中这个状态的概率，那么方程显然：

f(S) = \sum\limits_{k\in S} f(S - \{k\}) \cdot p_k

转移即可。

注意边界。当每个物品一定会被选中时候特判。

复杂度： O(2^n \times n)

STD

#include <iostream>
#include <iomanip>
using namespace std;
const int N = 20;
const long double eps = 1e-12;
long double f[1 << N], z[N], res[N];

int main (void)
{
    int n, k, cnt = 0;

    ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> z[i], cnt += z[i] > eps;
    if (cnt <= k) {
        for (int i = 0; i < n; i++) cout << (z[i] > eps ? "1.00 " : "0.00 ");
        return 0;
    }

    f[0] = 1;
    for (int i = 0; i < 1 << n; i++) {
        long double sum = 0;

        if (__builtin_popcount (i) == k) {
            for (int j = 0; j < n; j++) if (i & (1 << j)) res[j] += f[i];
            continue;
        }

    if (f[i] < eps) continue;
        for (int j = 0; j < n; j++) if (i & (1 << j)) sum += z[j];
        f[i] /= 1 - sum;
        for (int j = 0; j < n; j++) if (!(i & (1 << j))) f[i + (1 << j)] += f[i] * z[j];
    }

    cout << fixed << setprecision (2);
    for (int i = 0; i < n; i++) cout << res[i] << ' ';
    return 0;
}

G - 溶解

题意

求

\exp(\ln g \sum_{d\mid n} {n\choose d}) \bmod 1000000223

分析

设 P = 1000000223，由欧拉定理，原式即

\exp(\ln g \sum_{d\mid n} {n\choose d} \bmod \varphi(P)) \bmod P

其中，由于 P 是质数，\varphi(P) = P - 1。

就算是转换后，求指数里数也并不简单，况且 P - 1 不是质数。题目里已经给了 P - 1 的质因数分解，这时候我们应该能够想到分别求解四组同余方程，然后用 CRT 合并。

至于里头这个大组合数，明显 Lucas。

代码实现不难。

STD

#include <iostream>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
const ll p[4] = { 2, 13, 2797, 13751 }, T = 1000000222, P = T + 1;
ll a[4], fac[40000], x, y;

static void exgcd (ll a, ll b)
{
    ll t;
    if (!b) return x = 1, y = 0, void ();
    exgcd (b, a % b), t = x, x = y, y = t - a / b * y;
}

static inline ll inv (ll v, ll p) { return exgcd (v, p), (x + p) % p; }
static inline ll C (ll m, ll n, ll p) { return m > n ? 0 : fac[n] * inv (fac[m], p) % p * inv (fac[n - m], p) % p; }
static inline ll lucas (ll m, ll n, ll p) { return m ? lucas (m / p, n / p, p) * C (m % p, n % p, p) % p : 1; }
static ll fxp (ll a, ll b)
{
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % P;
        b >>= 1, a = a * a % P;
    }
    return res;
}

int main (void)
{
    ll res = 0, n, g;

    ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
    cin >> n >> g;
    if (g % P == 0) cout << "0\n", exit (0);

    for (int i = 0; i < 4; i++) {
        fac[0] = 1;
        for (int j = 1; j <= p[i]; j++) fac[j] = fac[j - 1] * j % p[i];

        for (ll q = 1; q * q <= n; q++) {
            ll y = q;
            if (n % y) continue;
            (a[i] += lucas (y, n, p[i])) %= p[i];
            if (y * y == n) continue;
            (a[i] += lucas (n / y, n, p[i])) %= p[i];
        }
    }

    for (int i = 0; i < 4; i++) (res += T / p[i] * inv (T / p[i], p[i]) % T * a[i] % T) %= T;
    cout << fxp (g, res) << '\n';
    return 0;
}

G - 水杯

题意

一个长度为 n 的序列，两种操作：

单点赋值
找 x 个数，每个数删掉一，问能不能重复 k 次。
分析

本场的数据结构压轴。

比较好分析。设大于等于 k 的数有 u 个，小于 k 的数和为 v，那么只要满足：

v \ge (x - u) \times k

在线可以用平衡树，离线可以用树状数组。本来想做强制在线，但是太毒瘤了。（但是赛时还是加了一个在线版本）

复杂度： O(n\log n)

STD

#include <iostream>
#include <cstring>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
int fa[N], son[N][2], siz[N], cntq[N], cnt = 1, rt;
ll qsum[N], val[N], z[N];

static inline void maintain (int x) { qsum[x] = qsum[son[x][0]] + qsum[son[x][1]] + val[x] * cntq[x], siz[x] = siz[son[x][0]] + siz[son[x][1]] + cntq[x]; }
static inline int get (int x) { return x == son[fa[x]][1]; }
static inline int compare (int f, int k) { return k > val[f]; }

void rotate (int x)
{
    int y = fa[x], z = fa[y], p = get (x);
    son[y][p] = son[x][p ^ 1];
    if (son[x][p ^ 1]) fa[son[x][p ^ 1]] = y;
    fa[fa[son[x][p ^ 1] = y] = x] = z;
    if (z) son[z][y == son[z][1]] = x;
    maintain (y), maintain (x);
}

int splay (int x, int t = 0)
{
    for (int f = fa[x]; (f = fa[x]) != t; rotate (x))
        if (fa[f] != t) rotate (get (x) == get (f) ? f : x);
    return t ? x : rt = x;
}

int insert_at (int f, ll k)
{
    qsum[cnt] = val[cnt] = k, siz[cnt] = cntq[cnt] = 1, fa[cnt] = f;
    if (f) son[f][compare (f, k)] = cnt;
    return cnt++;
}

int insert (int k)
{
    int f = rt, last = 0;
    if (!f) return rt = insert_at (0, k);
    while (f && val[f] != k) last = f, f = son[f][compare (f, k)];
    if (f && val[f] == k) return cntq[f]++, splay (f);
    else return f = insert_at (last, k), maintain (last), splay (f);
}

int find (int k)
{
    int f = rt;
    if (!f) return 0;
    while (son[f][compare (f, k)] && val[f] != k) f = son[f][compare (f, k)];
    return splay (f);
}

int merge (int x, int y)
{
    int f = x;
    if (!x || !y) return x + y;
    while (son[f][1]) f = son[f][1];
    splay (f, fa[x]);
    if (y) fa[y] = f;
    son[f][1] = y;
    return f;
}

int remove (int k)
{
    int f = find (k), x;
    if (val[f] != k) return 0;
    if (cntq[f] > 1) return cntq[f]--, splay (f);
    if ((x = merge (son[f][0], son[f][1]))) fa[x] = 0;
    return rt = x;   
}

int qpre (int k)
{
    int f = son[find (k)][0];
    if (val[rt] < k) return rt;
    while (son[f][1]) f = son[f][1];
    return f;
}

int qnext (int k)
{
    int f = son[find (k)][1];
    if (val[rt] > k) return rt;
    while (son[f][0]) f = son[f][0];
    return f;
}

int main (void)
{
    int n, m;

    ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
    cin >> n >> m;
    insert (0), insert (1e9);
    memset (z, 0x80, sizeof z);

    while (m--) {
        int t, x, y;

        cin >> t >> x >> y;
        if (t == 1) z[x] >= 0 ? remove (z[x]) : 0, insert (z[x] = y);
        else {
            int p = qpre (y), q = qnext (y);
            ll sum, k;
            splay (p), sum = qsum[p] - qsum[son[p][1]];
            splay (q, p), k = cntq[son[q][0]];
            splay (q), k += siz[q] - siz[son[q][0]] - 1;
            cout << (sum >= (x - k) * y ? "Yes" : "No") << '\n';
        }
    }
    return 0;
}

Niareh 的四月 题解

A - 回忆

题意

分析

STD

B - 街道

题意

分析

STD

C - 数环

题意

分析

STD

D - 周期

题意

分析

STD

F - 人偶

题意

分析

STD

G - 溶解

题意

分析

STD

G - 水杯

题意

分析

STD

Niareh 的四月题解