王清楚

发布于 2022-07-21 15:31

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

A

对于一个重量为 $k$ 的物品，他的生成函数为 $\frac{1}{1-x^k}$ 。

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

时间复杂度 $\mathcal O(n^2\log v+(150n)^2)$

#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

考虑期望 $\rm dp$ 。

设 $f_x$ 为当前非递减序列最后一个数是 $x$ ，之后能得到的期望数字个数。那么有转移方程：
$ $f_x=\sum_{i=1}^{x-1}1\times p_i+(1+f_x)p_x+\sum_{i=x+1}^n(1+f_i)p_i$ $其中第一部分是抽到比$ x $小的数，会立即停止操作。第二部分是仍然抽到$ x $，第三部分是抽到比$ x$ 大的数。

把 $dp_x$ 全部移到左边可以得到
$ $f_x=\frac{1+\sum_{i=x+1}^n p_i f_i}{1-p_x}$ $但是需要知道的是$ E(x^2) $，设他为$ g(x)$

因为 $E((x+1)^2)=E(x^2)+2E(x)+1$ ，所以可得
$ $g_x=\sum_{i=1}^{x-1}p_i +(g_x+2f_x+1)p_x+\sum_{i=x+1}^n (g_i+2f_i+1)p_i$ $再一次化简得到：$ $g_x=\frac{1+2f_xp_x+\sum_{i=x+1}^np_i(g_i+2f_i)}{1-p_x}$ $从后往前$ dp $，先求出$ f_x $，然后求出$ g_x$。

最终答案为：
$ $ans=\sum_{i=1}^np_i(1+2f_i+g_i)$ $
因为第一步可以抽到任意一个数。

#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

先假设 $x\geq y\geq z$

首先，如果 $x+y-n>z$ 那么无解。所以一定有 $x+y-n\leq z$

给三个串都加上 $z$ 个 $a$ ，就变成了长度为 $n-z$ ，三个 $\rm LCS$ 分别为 $x-z,y-z,0$ 的子问题。

因为 $x+y-n\leq z$ ，所以 $(x-z)+(y-z)\leq n-z$ 。

给前两个串放 $x-z$ 个 $b$ ，后两个串放 $y-z$ 个 $c$ 。

这样下来，第一个字符串长度为 $x$ ，第二个字符串长度为 $x+y-z$ ，第三个字符串长度为 $y$ 。并且 $\rm LCS$ 也满足条件。长度不够的用其他不冲突字符补上就好了。

#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

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

假设删掉 $k$ 条边，剩下连通块大小为 $a_1,a_2...a_{k+1}$

根据 $\rm prufer$ 序列可知方案数为 $n^{k-2}\prod_i^{k+1} a_i$

其中后面的 $\prod_i^{k+1}a_i$ 可以等价于，在 $k+1$ 个连通块中，每个连通块选一个点的方案数。

设 $dp[i][j][0/1]$ 表示以 $i$ 为根的子树内，删掉 $j$ 条边， $i$ 所在连通块是否已经选了点的方案数。树上背包转移即可。时间复杂度 $\mathcal O(nk)$ 。

#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

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

当 $a_1=x$ 时， $a_i'=a_i\oplus x$ 。那么需要找到满足所有 $l_i\leq a_i\oplus x\leq r_i$ 的 $x$ 的个数。

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

但发现在一些特殊的 $l,r$ 下，不等式可以同时异或一个数。那就是当 $l,r$ 的最高 $k$ 位相等，且 $l$ 剩下位数全是 $0$ ， $r$ 剩下位数全是 $1$ 的时候。那这就启发将 $l_i,r_i$ 拆成 $\mathcal O(\log n)$ 个这样的区间计算，并且这些区间不会相交。

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

#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

第一种操作会使边数 $-1$

第二种操作会使点数 $-k$ ，边数 $-(k-1)$

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

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

G

让我们考虑 $k=0$ 的特殊情况。
$ $\begin{aligned} \sum_{i=1}^na_i&=D(a_i\geq 0)\\ D!\prod_{i=1}^n\frac{1}{a_i!}&=n^D \end{aligned}$ $通过组合意义，发现下面的式子就是把$ D $个球分成$ n $组的方案数。那把$ a_i+k $看成一个数，就能类比得到如下式子：$ $\begin{aligned} \sum_{i=1}^na_i=D+nk(a_i\geq 0)\\ (D+nk)!\prod_{i=1}^n\frac{1}{a_i!}=n^{D+nk} \end{aligned}$ $但是求的答案必须满足$ a_i\geq k $才行。观察得到，$ n,k\leq 50$ ，数据范围都很小，不妨考虑容斥。

根据容斥步骤，需要钦定 $j$ 个不合法的 $a_i<k$ ，剩下的随便放，然后乘上容斥系数 $(-1)^j$ 。

设 $dp[i][j]$ 表示钦定 $i$ 组不合法，他们的和是 $j$ 的方案数。最终答案就是
$ $\frac{D!}{(D+nk)!}\sum_{i=0}^n(-1)^i\sum _{j=0}^{i\times (k-1)}dp[i][j]\binom{n}{i}\binom{D+nk}{j}(n-i)^{D+nk-j}$ $因为最终答案乘上的是$ D! $，所以最外面需要更改系数。然后第一个循环枚举不合法的$ a_i $个数，第二个循环枚举它们的和，然后从盒子里选$ i $个不合法，从球里选$ j $个装进去，剩下的随便放。时间复杂度$ \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

有 $x\otimes y=\frac{xy}{\gcd(x,y)^2}$ 。枚举 $x'=\frac{x}{\gcd(x,y)},y'=\frac{y}{\gcd (x,y)}$ 。那么有：
$ $b_k=\sum_{x'y'=k}\sum_{d=1}^{\lfloor\frac{n}{\max(x',y')}\rfloor}a_{x'd}(y'd)^c[\gcd(x',y')=1]$ $前面的枚举是$ \mathcal O(n\log n) $的。考虑快速计算后者（假设$ x>y,m=\lfloor \frac{n}{x}\rfloor $）$ $\begin{aligned} &\sum_{d=1}^m a_{xd}(yd)^c\\ =&(\sum_{d=1}^m a_{xd}d^c)y^c\\ =&(\sum_{d=1}^ma_{xd}(xd)^c)\times \frac{y^c}{x^c} \end{aligned}$ $预处理$ f_{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

若把某个 $x$ 加一，只可能影响 $x$ 与 $x+1$ 的关系。即当 $x+1$ 在 $x$ 前面时，操作 $x$ ，不操作 $x+1$ 可以使逆序对 $-1$ 。若对于 $x+1$ 在 $x$ 前面这样的点对 $(x,x+1)$ 连边，最终的图由几条链构成。一条长为 $m$ 的链最多让逆序对数减少 $\lfloor\frac{m}{2}\rfloor$ 。

#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

考虑快速计算一个子矩阵的答案。
$ $\begin{aligned} &\sum_{i=l_1}^{r_1}\sum_{j=l_2}^{r_2}a_i+b_j\times \frac{1}{(r_1-l_1+1)(r_2-l_2+1)}\\ =&\Big(\sum_{i=l_1}^{r_1}a_i(r_2-l_2+1)\sum_{j=l_2}^{r_2}b_j(r_1-l_1+1)\Big )\times \frac{1}{(r_1-l_1+1)(r_2-l_2+1)}\\ =&\sum_{i=l_1}^{r_1}a_i\frac{1}{r_1-l_1+1}\sum_{j=l_2}^{r_2}b_j\frac{1}{(r_2-l_2+1)} \end{aligned}$ $发现问题变成了两部分，在$ a $里面找长度至少为$ x $的，平均值最大的区间，$ b$ 同理。

这是个经典问题，二分答案 $mid$ ，所有数减去 $mid$ ，区间和大于等于 $0$ 等价于区间平均值大于等于 $mid$ 。时间复杂度 $\mathcal O(n\log V)$

#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));
}

2026最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(0) 回帖

加载中...

话题同步到我的动态回帖

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

A

B

C

D

E

F

G

H

I

J

已采纳

精彩回帖

全部评论

本文相关内容

等你来战

热门推荐