竞赛讨论区 > 【题解】2021牛客暑期多校训练营4
头像
王清楚
发布于 07-21 15:31
+ 关注

【题解】2021牛客暑期多校训练营4

A

对于一个重量为 的物品,他的生成函数为

对于以 为根的子树,设答案的生成函数为 。那么如果要更新一个点的答案,先把他所有儿子的生成函数乘起来,求出前 项,然后直接剪掉即可。最后得到 ,用线性递推算第 项即可。

时间复杂度

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
const int P = 998244353;
int X[555], Y[555];
int len = 1, rev[N], ans[N];
vector<int> dp[111], e[111];
int lim, s[111], c[111];
int inv(int x, int base = P - 2) {
    int res = 1;

    while (base) {
        if (base & 1)
            res = 1ll * res * x % P;

        x = 1ll * x * x % P;
        base >>= 1;
    }

    return res;
}
void init() {
    for (int i = 0; i < len; i++) {
        rev[i] = rev[i >> 1] >> 1;

        if (i & 1)
            rev[i] |= (len >> 1);
    }
}
void NTT(vector<int> &x, int op) {
    for (int i = 0; i < len; i++)
        if (i < rev[i])
            swap(x[i], x[rev[i]]);

    for (int i = 2; i <= len; i <<= 1) {
        int mid = i >> 1;
        int wn = inv(3, (P - 1) / i);

        if (op == -1)
            wn = inv(wn, P - 2);

        for (int j = 0; j < len; j += i) {
            for (int k = j, now = 1; k < j + mid; k++) {
                int aa = x[k], bb = 1ll * x[k + mid] * now % P;
                now = 1ll * now * wn % P;
                x[k] = (aa + bb) % P;
                x[k + mid] = (aa - bb + P) % P;
            }
        }
    }

    if (op == -1) {
        int INV = inv(len);

        for (int i = 0; i < len; i++)
            x[i] = 1ll * x[i] * INV % P;
    }
}
vector<int> mul(vector<int> a, vector<int> b) {
    vector<int> c;
    int Lim = a.size() + b.size();
    len = 1;

    while (len < Lim)
        len <<= 1;

    init();
    a.resize(len + 1);
    b.resize(len + 1);
    c.resize(len + 1);
    NTT(a, 1);
    NTT(b, 1);

    for (int i = 0; i <= len; i++)
        c[i] = 1ll * a[i] * b[i] % P;

    NTT(c, -1);
    return c;
}
void dfs(int rt) {
    dp[rt].resize(lim + 1);

    for (int i = 0; i <= lim; i += s[rt])
        dp[rt][i] = 1;

    for (int i = 0; i < e[rt].size(); i++) {
        int v = e[rt][i];
        dfs(v);
        dp[rt] = mul(dp[v], dp[rt]);
        dp[rt].resize(lim + 1);
    }

    for (int i = 0; i < c[rt]; i++)
        dp[rt][i] = 0;
}
int cal(int num, int x[], int y[], int id) {
    int ans = 0;

    for (int i = 1; i <= num; i++) {
        int res1 = y[i], res2 = 1;

        for (int j = 1; j <= num; j++) {
            if (i == j)
                continue;

            res1 = 1ll * res1 * ((id - x[j] + P) % P) % P;
            res2 = 1ll * res2 * ((x[i] - x[j] + P) % P) % P;
        }

        ans += 1ll * res1 * inv(res2) % P;

        if (ans >= P)
            ans -= P;
    }

    return ans;
}
int Fa[N], rt;
signed main() {
    lim = 50000;
    int n, q;
    scanf("%d%d", &n, &q);

    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        e[u].push_back(v);
        Fa[v] = 1;
    }

    for (int i = 1; i <= n; i++)
        if (!Fa[i])
            rt = i;

    for (int i = 1; i <= n; i++)
        scanf("%d", &s[i]);

    for (int i = 1; i <= n; i++)
        scanf("%d", &c[i]);

    dfs(rt);

    while (q--) {
        int w;
        scanf("%d", &w);

        if (w <= lim)
            printf("%d", dp[rt][w]);
        else {
            int j;

            for (j = 10000; j <= 10000 + 60; j++)
                if (j % 60 == w % 60)
                    break;

            for (int i = 1; i <= n + 1; i++) {
                X[i] = j;
                Y[i] = dp[rt][j];
                j += 60;
            }

            printf("%d", cal(n + 1, X, Y, w));
        }

        puts("");
    }
}

B

考虑期望

为当前非递减序列最后一个数是 ,之后能得到的期望数字个数。那么有转移方程:
$xxx$ 大的数。

全部移到左边可以得到
$E(x^2)g(x)$

因为 ,所以可得
$dpf_xg_x$。

最终答案为:
$$
因为第一步可以抽到任意一个数。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int p = 998244353;
int n, F = 1, c, sum;
int a[101];
int inv(int x, int base = p - 2) {
    int res = 1;

    while (base) {
        if (base & 1)
            res = res * x % p;

        x = x * x % p;
        base >>= 1;
    }

    return res;
}
signed main() {
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> a[i], sum += a[i];

    for (int i = 0; i < n; i++)
        F = F * sum % p * inv(sum - a[i]) % p, c += a[i] * inv(sum - a[i]);

    cout << (c % p * 2 * F + F) % p << endl;
}

C

先假设

首先,如果 那么无解。所以一定有

给三个串都加上 ,就变成了长度为 ,三个 分别为 的子问题。

因为 ,所以

给前两个串放 ,后两个串放

这样下来,第一个字符串长度为 ,第二个字符串长度为 ,第三个字符串长度为 。并且 也满足条件。长度不够的用其他不冲突字符补上就好了。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b, c, n;
    cin >> a >> b >> c >> n;
    int minn = min(a, min(b, c));

    if (b + c + a - 2 * minn > n) {
        puts("NO");
        return 0;
    }

    string s1, s2, s3;
    s1 = string(a, 'a') + string(c - minn, 'b');
    s2 = string(a, 'a') + string(b - minn, 'c');
    s3 = string(minn, 'a') + string(b - minn, 'c') + string(c - minn, 'b');
    s1 += string(n - s1.length(), 'x');
    s2 += string(n - s2.length(), 'y');
    s3 += string(n - s3.length(), 'z');
    cout << s1 << endl;
    cout << s2 << endl;
    cout << s3 << endl;
}

D

前考虑删掉指定的 条边后,再加 条边还是树的方案数。

假设删掉 条边,剩下连通块大小为

根据 序列可知方案数为

其中后面的 可以等价于,在 个连通块中,每个连通块选一个点的方案数。

表示以 为根的子树内,删掉 条边, 所在连通块是否已经选了点的方案数。树上背包转移即可。时间复杂度

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 9;
const int p = 998244353;
int n, k, sz[N];
vector<int> e[N];
int f[N][105][2], g[105][2];
void dfs(int x, int fa) {
    sz[x] = 1;
    f[x][1][0] = f[x][1][1] = 1;

    for (int to : e[x])
        if (to != fa) {
            dfs(to, x);
            memcpy(g, f[x], sizeof(g));
            memset(f[x], 0, sizeof(f[x]));

            for (int a = 1; a <= min(sz[x], k + 1); a++)
                for (int b = 1; b <= min(sz[to], k + 1) && a + b - 1 <= k + 1; b++) {
                    f[x][a + b - 1][0] = (f[x][a + b - 1][0] + 1ll * g[a][0] * f[to][b][0]) % p;
                    f[x][a + b - 1][1] = (f[x][a + b - 1][1] + 1ll * g[a][0] * f[to][b][1]) % p;
                    f[x][a + b - 1][1] = (f[x][a + b - 1][1] + 1ll * g[a][1] * f[to][b][0]) % p;
                    f[x][a + b][0] = (f[x][a + b][0] + 1ll * g[a][0] * f[to][b][1]) % p;
                    f[x][a + b][1] = (f[x][a + b][1] + 1ll * g[a][1] * f[to][b][1]) % p;
                }

            sz[x] += sz[to];
        }
}
int main() {
    scanf("%d%d", &n, &k);

    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        e[x].push_back(y);
        e[y].push_back(x);
    }

    dfs(1, 0);
    int ans = f[1][k + 1][1];

    for (int i = 1; i < k; i++)
        ans = 1ll * ans * n % p;

    cout << ans << endl;
}

E

容易发现,只要确定树上一个点的权值,那么整棵树的权值也就确定了。不妨假设 ,先求出一个初始答案。

时,。那么需要找到满足所有 的个数。

但是不能在不等式上同时异或一个数。否则直接异或上 就可以求出答案了。

但发现在一些特殊的 下,不等式可以同时异或一个数。那就是当 的最高 位相等,且 剩下位数全是 剩下位数全是 的时候。那这就启发将 拆成 个这样的区间计算,并且这些区间不会相交。

最后合法的 满足覆盖他的区间个数为 ,就差分计算答案即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
const int M = (1 << 30) - 1;
int n, L[N], R[N];
vector<pair<int, int>>p, G[N];
void insert(int a, int b) {
    int res = a ^ b;

    for (int i = 0; i < 30; ++i) {
        int t = res ^ (1 << i) ^ (res & ((1 << i) - 1));

        if ((t ^ a) > b)
            p.push_back({t, t + (1 << i) - 1});
    }
}
void dfs(int x, int fa, int k) {
    insert(k, R[x]), insert(M ^ k, M ^ L[x]);

    for (auto it : G[x])
        if (it.first != fa)
            dfs(it.first, x, k ^ it.second);
}
int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &L[i], &R[i]);

    for (int i = 1; i < n; ++i) {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w),
              G[x].emplace_back(y, w), G[y].emplace_back(x, w);
    }

    dfs(1, 0, 0);
    sort(p.begin(), p.end());
    int ans = 0, x = 0;

    for (auto it : p) {
        int l = it.first, r = it.second;

        if (l > x)
            ans += l - x - 1;

        x = max(x, r);
    }

    if (x < M)
        ans += M - x;

    cout << ans << endl;
    return 0;
}

F

第一种操作会使边数

第二种操作会使点数 ,边数

两种操作都会使得 奇偶性改变。所以最终答案只和 的奇偶性有关。

#include<bits/stdc++.h>
using namespace std;
int a, b;
int main(){
    cin >> a >> b;
    puts( (a + b) & 1 ? "Alice" : "Bob");
    return 0;
}

G

让我们考虑 的特殊情况。
$Dna_i+ka_i\geq kn,k\leq 50$ ,数据范围都很小,不妨考虑容斥。

根据容斥步骤,需要钦定 个不合法的 ,剩下的随便放,然后乘上容斥系数

表示钦定 组不合法,他们的和是 的方案数。最终答案就是
$D!a_iij\mathcal O((nk)^2)$

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5e2 + 9;
const int p = 998244353;
int n, k, d, f[55][N], ans;
int inv(int x, int base = p - 2) {
    int res = 1;

    while (base) {
        if (base & 1)
            res = 1ll * res * x % p;

        x = 1ll * x * x % p;
        base >>= 1;
    }

    return res;
}
int fac[30010], ifac[30010];
void init(int n = 30000) {
    fac[0] = 1;

    for (int i = 1; i <= n; i++)
        fac[i] = 1ll * fac[i - 1] * i % p;

    ifac[n] = inv(fac[n]);

    for (int i = n - 1; i >= 0; i--)
        ifac[i] = 1ll * ifac[i + 1] * (i + 1) % p;

    assert(1ll * fac[10]*ifac[10] % p == 1);
}
int C(int n, int m) {
    return n >= m && m >= 0 ? 1ll * fac[n] * ifac[m] % p * ifac[n - m] % p : 0;
}
int main() {
    scanf("%d%d%d", &n, &k, &d);
    init();
    d += n * k;
    f[0][0] = 1;

    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= i * (k - 1); ++j)
            for (int l = min(j, k - 1); ~l; --l)
                f[i][j] = (1ll * f[i - 1][j - l] * C(j, l) + f[i][j]) % p;

    for (int i = 0; i <= n; ++i) {
        for (int j = 0, res = 1; j <= i * (k - 1); ++j) {
            ans = (ans + (i & 1 ? -1ll : 1ll) * C(n, i) * f[i][j] % p * res % p * inv(n - i, d - j)) % p;
            res = 1ll * res * (d - j) % p * inv(j + 1) % p;
        }
    }

    for (int i = 0; i < n * k; ++i)
        ans = 1ll * ans * inv(d - i) % p;

    printf("%d\n", (ans + p) % p);
    return 0;
}

H

。枚举 。那么有:
$\mathcal O(n\log n)x>y,m=\lfloor \frac{n}{x}\rfloorf_{x,m}(\sum_{d=1}^ma_{xd}(xd)^c)\mathcal O(n\log n)$

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int P = 998244353;
const int N = 1e6 + 9;
int dp[N];
int n, a[N], p[N], b[N], c;
int inv(int x, int base = P - 2) {
    int res = 1;

    while (base) {
        if (base & 1)
            res = 1ll * res * x % P;

        x = 1ll * x * x % P;
        base >>= 1;
    }

    return res;
}

signed main() {
    cin >> n >> c;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = inv(i, c);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n / i; j++) {
            dp[j] = (dp[j - 1] + a[i * j] * p[j] % P) % P;
        }

        for (int j = 1; j <= n / i; j++)
            if (__gcd(i, j) == 1) {
                b[i * j] = (b[i * j] + p[j] * dp[min(n / i, n / j)] % P) % P;
            }
    }

    for (int i = 1; i <= n; i++)
        b[i] ^= b[i - 1];

    cout << b[n];
}

I

若把某个 加一,只可能影响 的关系。即当 前面时,操作 ,不操作 可以使逆序对 。若对于 前面这样的点对 连边,最终的图由几条链构成。一条长为 的链最多让逆序对数减少

#include <bits/stdc++.h>
#define lowbit(x) (x&-x)
using namespace std;
const int N = 2e5 + 9;
int n;
long long ans;
int a[N], b[N], c[N];
void add(int x) {
    while (x <= n)
        c[x]++, x += lowbit(x);
}
int get(int x, int res = 0) {
    while (x)
        res += c[x], x -= lowbit(x);

    return res;
}
int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);

    for (int i = n; i >= 1; --i) {
        if (!b[a[i] - 1])
            b[a[i]] = 1, a[i]++;
    }

    for (int i = n; i >= 1; --i) {
        add(a[i]);
        ans += get(a[i] - 1);
    }

    printf("%lld\n", ans);
    return 0;
}

J

考虑快速计算一个子矩阵的答案。
$axb$ 同理。

这是个经典问题,二分答案 ,所有数减去 ,区间和大于等于 等价于区间平均值大于等于 。时间复杂度

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 0;
const double eps = 1e-8;
int n, m, x, y;
int a[N];
double sum[N];
bool check(int k, double mid, int n) {
    double res, mn = 0.0;

    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + a[i] - mid;

    res = sum[n];

    for (int i = n + 1; i <= k; i++) {
        mn = min(mn, sum[i - n]);
        sum[i] = sum[i - 1] + a[i] - mid;
        res = max(res, sum[i] - mn);
    }

    return res >= 0;
}
double wrok(int k, int n) {
    double l = 0.0, r = 100001.0;

    for (int i = 1; i <= k; i++)
        scanf("%d", &a[i]);

    while (r - l > eps) {
        double mid = (l + r) / 2.0;

        if (check(k, mid, n))
            l = mid;
        else
            r = mid;
    }

    return r;
}
int main() {
    scanf("%d%d%d%d", &n, &m, &x, &y);
    printf("%.10lf\n", wrok(n, x) + wrok(m, y));
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐