2021-08-27 17:31 已编辑北京大学 C++

关注

牛客多校第九场题解

A A Math Challenge

题意：给定 $n,a,b,c,p,q$ ，求 $\displaystyle \sum_{i=0}^n \sum_{j=1}^{\lfloor \frac{ai+b}{c}\rfloor} i^p j^q$ 。

解法：遇到 $\displaystyle \lfloor \frac{ai+b}{c} \rfloor$ 的式子，通常想到类欧几里得算法。此法的核心在于可以将这类的求和在 $O(\log n)$ 的时间内算出。

朴素的类欧几里得算法是计算 $f(n,a,b,c)=\displaystyle \sum_{i=1}^n \lfloor \frac{ai+b}{c} \rfloor$ 的。边界条件即是 $a=0$ ，此时答案等于 $\displaystyle \lfloor \frac{b}{c} \rfloor \frac{n(n-1)}{2}$ 。考虑以下两种转移：

$a \geq c$ 或 $b \geq c$ 。将 $\displaystyle \lfloor \frac{ai+b}{c} \rfloor$ 化成 $\displaystyle \lfloor \frac{(a \mod c)i+b \mod c}{c}+\lfloor \frac{a}{c} \rfloor i +\lfloor \frac{b}{c} \rfloor \rfloor=\lfloor \frac{(a \mod c)i+b \mod c}{c} \rfloor +\lfloor \frac{a}{c} \rfloor i+ \lfloor \frac{b}{c} \rfloor$ ，因而有 $\displaystyle f(n,a,b,c)=f(n,a \mod c,b,c)+ \sum_{i=1}^n (\lfloor \frac{a}{c} \rfloor i+\lfloor \frac{b}{c} \rfloor)=f(n,a\mod c,b,c)+\lfloor \frac{a}{c} \rfloor\frac{n(n-1)}{2}+\lfloor \frac{b}{c} \rfloor n$ 。
$a<c$ 且 $b<c$ 。可以证明， $\displaystyle f(n,a,b,c)=n \lfloor \frac{an+b}{c} \rfloor-f(\lfloor \frac{an+b}{c} \rfloor-1, c,c-b-1,a)$ 。容易发现， $a,c$ 交换了位置，并且每次折半，因而可以做到 $O(\log n)$ 的复杂度。

记 $f(n,a,b,c,p,q)=\displaystyle \sum_{i=0}^n \sum_{j=1}^{\lfloor \frac{ai+b}{c}\rfloor} i^p j^q$ ， $\displaystyle S(n,k)=\sum_{i=1}^{n} i^k$ 。依旧考虑上面的两种转移（此时细分为三种）：

$b\geq c$ 。我们想要将 $b$ 变成 $b \mod c$ ，想象一个 $\displaystyle y=\lfloor \frac{b}{c} \rfloor$ 截取整个区域： $y=ax+b,y=0:x=0,x=n$ ，则会有一部分矩形区域 $\displaystyle [0,\lfloor \frac{b}{c} \rfloor ]:[1,n]$ ，这部分和为 $\displaystyle \sum_{i=0}^n \sum_{j=1}^{\lfloor \frac{b}{c} \rfloor} i^pj^q=S(n,p)S(\lfloor \frac{b}{c} \rfloor,q)$ ，因而直接累加上去即可。此时剩余的部分即是 $\displaystyle \sum_{i=0}^n \sum_{j=1}^{b \mod c}i^p(j+\lfloor \frac{b}{c} \rfloor)^q$ 。令 $\displaystyle r=\lfloor \frac{b}{c} \rfloor$ ，将 $(j+r)^q$ 进行二项式展开，可以得到 $\displaystyle \sum_{k=0}^q \dbinom{q}{k} r^{q-k}f(n,a,b \mod c,p,k)$ 。
$a\geq c$ 。此时截取的直线为 $\displaystyle y=\lfloor \frac{a}{c} \rfloor x$ ，记 $\displaystyle r=\lfloor \frac{a}{c}\rfloor$ ，其下方区域的的值为 $\displaystyle \sum_{i=0}^n \sum_{j=1}^{ki}i^pj^q$ 。记 $\displaystyle S(n,q)=\sum_{i=0}^{q+1} c_in^i$ ，则原式等于 $\displaystyle \sum_{i=1}^n i^p \sum_{j=0}^{q+1}c_j(ri)^j=\sum_{j=0}^{q+1}c_jr^j \sum_{i=1}^{n}i^{j+p}=\sum_{j=0}^{q+1} c_j r^j S(n,j+p)$ 。剩下的部分 $\displaystyle \sum_{i=0}^n \sum_{j=1}^{b \mod c}i^p(j+\lfloor \frac{a}{c} \rfloor i)^q$ 。同样是二项式展开，有 $\displaystyle \sum_{k=0}^q \dbinom{q}{k} r^{q-k} f(n,a \mod c,b,c,p+q-k,k)$ 。
$a<c$ 且 $b<c$ 。根据求解 $\gcd$ 的欧几里得算法，我们将 $a,b$ 互换然后取模，因而这里也要进行类似操作。此部分需要将区间向左平移一个单位再沿着 $y=x$ 翻转（对应着交换操作），此时区间变成 $\displaystyle [1,\lfloor \frac{an+b}{c} \rfloor ]:[0,n]$ 。划下一个矩形部分 $\displaystyle \sum_{i=1}^{\lfloor \frac{an+b}{c} \rfloor } i^q \sum_{j=0}^nj^p=S(\lfloor \frac{an+b}{c} \rfloor ,q)S(n,p)$ 。令 $\displaystyle m=\lfloor \frac{an+b}{c} \rfloor$ 剩余部分，即是 $\displaystyle \sum_{i=0}^n \sum_{j=1}^{m}j^p(i+1)^q$ 。继续做二项式展开，可以得到 $\displaystyle \sum_{k=1}^q \dbinom{q}{k} f(m-1,c,c-b-1,a,k,p)$ 。

因而记忆化 $f(n,a,b,c,p,q)$ ，使用这一算法即可。

C Cells

题意：有 $2n$ 个点 $\{ A_n\}$ 与 $\{B_n\}$ ，满足 $A_i(a_i,0)$ ， $B_i(0,i)$ ，问 $\forall i \in [1,n]$ ， $A_i$ 到 $B_i$ 路径不相交的方案数。 $n \leq 5\times 10^5$ 。

解法：涉及不相交路径计数问题，需要使用到 LGV 引理。记 $e(A,B)$ 为 $A$ 到 $B$ 的路径方案数，则所有点对路径都不相交的方案数为：

$\begin{vmatrix} e(A_1,B_1) & e(A_1,B_2) & e(A_1,B_3) & \cdots & e(A_1,B_n) \\ e(A_2,B_1) & e(A_2,B_2) & e(A_2,B_3) & \cdots & e(A_2,B_n) \\ e(A_3,B_1) & e(A_3,B_2) & e(A_3,B_3) & \cdots & e(A_3,B_n) \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ e(A_n,B_1) & e(A_n,B_2) & e(A_n,B_3) & \cdots & e(A_n,B_n) \\ \end{vmatrix}$

在此题中， $e(A_i,B_j)=\dbinom{a_i+1}{j}$ ，因而考虑手动化简上式。

先将每一列组合数下方的阶乘 $i!$ 提出，再提出每一行的公因式 $a_i+1$ ，原矩阵可化为：

$\frac{\prod_{i=1}^n(a_i+1)}{\prod_{i=1}^n i!} \begin{vmatrix} 1 & a_1 & a_1^2& \cdots & a_1^{n-1} \\ 1 & a_2 & a_2^2& \cdots & a_2^{n-1} \\ 1 & a_3 & a_3^2& \cdots & a_3^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & a_n & a_n^2& \cdots & a_n^{n-1} \\ \end{vmatrix}$

这是由于 $\dbinom{a_i+1}{j}$ 都是一个 $a_i$ 的 $j$ 次多项式。有了第一列的 $1$ ，可以将第二列的常数项消去，得到 $a_i$ ；再利用第一列和第二列的常数项、一次项可以将第二列的二次多项式消成 $a_i^2$ ，以此类推可以得到上式。

容易发现后面的行列式就是范德蒙行列式，其值等于 $\displaystyle \prod_{1 \leq i < j \leq n}(a_i-a_j)$ 。由于 $n$ 太大，因而只能采用多项式卷积的方法计算出每一个差值极其对应的次数。

整体复杂度 $O(n \log n)$ 。

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double pi = acos(-1);
const long long mod = 998244353;
struct complex
{
    double x;
    double y;
};
struct complex f[4000005], g[4000005];
int r[4000005];
complex operator +(complex a,complex b)
{
    return (complex){a.x + b.x, a.y + b.y};
}
complex operator -(complex a,complex b)
{
    return (complex){a.x - b.x, a.y - b.y};
}
complex operator *(complex a,complex b)
{
    return (complex){a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x};
}
void FFT(complex *J,int times,int flag)
{
    for (int i = 1; i < times;i++)
        if(i<r[i])
            swap(J[i], J[r[i]]);

    for (int i = 1; i < times; i <<= 1)
    {
        complex unit = (complex){cos(flag * pi / i), sin(flag * pi / i)};
        for (int j = 0; j < times; j += i * 2)
        {
            complex w = (complex){1, 0};
            for (int k = 0; k < i; k++, w = w * unit)
            {
                complex x = J[j + k], y = w * J[j + i + k];
                J[j + k] = x + y;
                J[j + k + i] = x - y;
            }
        }
    }
}
long long a[500005], fac[500005], invfac[500005];
long long power(long long a, long long x)
{
    long long ans = 1;
    while(x)
    {
        if(x&1)
            ans = ans * a % mod;
        a = a * a % mod;
        x >>= 1;
    }
    return ans;
}
long long inv(long long a)
{
    return power(a, mod - 2);
}
int main()
{
    int n, times = 1, left = 0;
    scanf("%d", &n);
    long long ans = 1;
    for (int i = 1; i <= n;i++)
    {
        scanf("%lld", &a[i]);
        f[a[i]].x = g[1000000 - a[i]].x = 1;
        ans = ans * (a[i] + 1) % mod;
    }
    fac[0] = fac[1] = 1;
    for (int i = 1; i <= n;i++)
        fac[i] = fac[i - 1] * i % mod;
    invfac[n] = inv(fac[n]);
    for (int i = n - 1; i >= 1;i--)
        invfac[i] = invfac[i + 1] * (i + 1) % mod;
    for (int i = 1; i <= n;i++)
        ans = ans * invfac[i] % mod;
    while (times <= 2000002)
    {
        times <<= 1;
        left++;
    }
    for (int i = 0; i < times; i++)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (left - 1));
    FFT(f, times, 1);
    FFT(g, times, 1);
    for (int i = 0; i <= times; i++)
        f[i] = f[i] * g[i];
    FFT(f, times, -1);
    for (int i = 1000001; i <= 2000000; i++)
    {
        int temp = (int)(f[i].x / times + 0.5);
        ans = ans * power(i - 1000000, temp) % mod;
    }
    printf("%lld", ans);
    return 0;
}

E Eyjafjalla

题意：有一个 $n$ 个节点的树， $1$ 号节点温度最高，其余的依次降低——越靠近 $1$ 号节点温度越高。 $q$ 次询问，问从 $x$ 节点出发温度范围在 $[l,r]$ 的节点个数。 $n,q \leq 1 \times 10^5$ 。

解法：由于温度的单调性，一定是先根据 $r$ ，走到 $x$ 最上面的节点（深度最低的节点），然后查询其子树，查询子树中满足温度大于等于 $l$ 的节点个数。因为已经走到了最上面的节点，因而温度上限是不必要的。

这一问题可以通过离线来完成。将全部询问离线下来，根据查询温度 $l$ 的高低，从高到低的回答询问。每次将温度大于等于 $l$ 的节点插入，然后查询子树中节点的数目即可。由于是查询子树，修改子树，因而可以考虑使用欧拉序列来完成。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100000;
struct line
{
    int from;
    int to;
    int next;
};
struct line que[N * 2 + 5];
struct node
{
    int id;
    int t;
    bool operator <(const node &b)const
    {
        return t > b.t;
    }
};
struct node city[N + 5];
struct ask
{
    int id;
    int place;
    int l;
    int r;
    bool operator <(const ask &b)const
    {
        return l > b.l;
    }
};
struct ask list[N + 5];
int cnt, headers[N + 5];
void add(int from,int to)
{
    cnt++;
    que[cnt].from = from;
    que[cnt].to = to;
    que[cnt].next = headers[from];
    headers[from] = cnt;
}
int st[N + 5], ed[N + 5], ind;
int father[25][N + 5];
int depth[N + 5];
void dfs(int place,int fa)
{
    st[place] = ++ind;
    father[0][place] = fa;
    for (int i = 1; i <= 20; i++)
        father[i][place] = father[i - 1][father[i - 1][place]];
    depth[place] = depth[fa] + 1;
    for (int i = headers[place]; i;i=que[i].next)
        if(que[i].to!=fa)
            dfs(que[i].to, place);   
    ed[place] = ++ind;
}
int t[N * 8 + 5];
void change(int place,int left,int right,int start,int x)
{
    if (left==right)
    {
        t[place] += x;
        return;
    }
    int mid = (left + right) >> 1;
    if(start<=mid)
        change(place << 1, left, mid, start, x);
    else
        change(place << 1 | 1, mid + 1, right, start, x);
    t[place] = t[place << 1] + t[place << 1 | 1];
}
int query(int place,int left,int right,int start,int end)
{
    if(start<=left && right<=end)
        return t[place];
    int mid = (left + right) >> 1;
    int ans = 0;
    if(start<=mid)
        ans += query(place << 1, left, mid, start, end);
    if(end>mid)
        ans += query(place << 1 | 1, mid + 1, right, start, end);
    return ans;
}
int ans[N + 5];
int main()
{
    int n, u, v, q;
    scanf("%d", &n);
    for (int i = 1; i < n;i++)
    {
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    dfs(1, 1);
    for (int i = 1; i <= n;i++)
    {
        scanf("%d", &city[i].t);
        city[i].id = i;
    }
    scanf("%d", &q);
    for (int i = 1; i <= q;i++)
    {
        scanf("%d%d%d", &u, &list[i].l, &list[i].r);
        if(city[u].t<list[i].l || city[u].t>list[i].r)
            continue;
        list[i].id = i;
        int place = u;
        for (int j = 20; j >= 0; j--)
            if (father[j][place] && city[father[j][place]].t <= list[i].r)
                place = father[j][place];
        list[i].place = place;
    }
    sort(city + 1, city + n + 1);
    sort(list + 1, list + q + 1);
    int place = 1;
    for (int i = 1; i <= q;i++)
    {
        while (place <= n && city[place].t >= list[i].l)
        {
            change(1, 1, ind, st[city[place].id], 1);
            place++;
        }
        if(!list[i].place)
            continue;
        ans[list[i].id] = query(1, 1, ind, st[list[i].place], ed[list[i].place]);
    }
    for (int i = 1; i <= q;i++)
        printf("%d\n", ans[i]);
    return 0;
}

G Glass Balls

题意：给定一个以 $1$ 为根节点的 $n$ 节点树，每个节点初始都放有一个球，每个节点有 $p$ 的概率可以销毁当前这一位置上的球。现在这些球向下滚，以 $1$ 的速度走向它的父亲，如果在某一时刻有两个球出现在同一节点，发生碰撞，则该局记 $0$ 分。否则，分数为 $\displaystyle \sum_{i=1}^n f(i)$ ，其中 $f(i)$ 为从 $i$ 号节点出发走过的路径长。问得分的期望。

解法：首先考虑不得 $0$ 分的情况——记 $P_i$ 为 $i$ 节点的子树中都不出现碰撞事件的概率。则容易得到其概率为儿子节点全部可以销毁球或者只有一个不能销毁球。

设计一个树形期望 DP—— $f_i$ 表示子树都没有出现碰撞事件的前提下，当前节点的球往下滚动了一位，其子树的分数期望。那么它的转移为子树的 $f_x$ 的和，乘以刚好有一个儿子的球能滚下的概率（只能有一个儿子的球滚到自己这里），再除以不碰撞的概率（条件概率公式），再无条件加一（表示自己这一位上球的滚动）。

最后答案就是 $P_1(\displaystyle \sum_{i=1}^nf_i-1)$ 。这是因为我们要考虑当前这一节点无球往下滚动的情况。

总复杂度 $O(n)$ 。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 500000;
const long long mod = 998244353;
long long power(long long a,long long x)
{
    long long ans = 1;
    while(x)
    {
        if(x&1)
            ans = ans * a % mod;
        a = a * a % mod;
        x >>= 1;
    }
    return ans;
}
long long inv(long long a)
{
    return power(a, mod - 2);
}
struct line
{
    int from;
    int to;
    int next;
};
struct line que[N * 2 + 5];
int cnt, headers[N + 5];
void add(int from,int to)
{
    cnt++;
    que[cnt].from = from;
    que[cnt].to = to;
    que[cnt].next = headers[from];
    headers[from] = cnt;
}
long long p[N + 5], f[N + 5], P;
void dfs(int place,int father)
{
    int child = 0;
    long long temp = 0;
    p[place] = 1;
    for (int i = headers[place]; i;i=que[i].next)
        if(que[i].to!=father)
        {
            child++;
            dfs(que[i].to, place);
            p[place] = p[place] * p[que[i].to] % mod;
            temp = (temp + f[que[i].to]) % mod;
        }
    if(!child)
    {
        f[place] = 1;
        return;
    }
    long long ava = (power(P, child) + power(P, child - 1) * (1 - P + mod) % mod * child % mod) % mod;
    p[place] = (p[place] * ava) % mod;
    f[place] = (1 + temp * inv(ava) % mod * power(P, child - 1) % mod * (1 - P + mod) % mod) % mod;
    return;
}
int main()
{
    int n, u;
    scanf("%d%lld", &n, &P);
    for (int i = 2; i <= n;i++)
    {
        scanf("%d", &u);
        add(i, u);
        add(u, i);
    }
    dfs(1, 1);
    long long ans = 0;
    for (int i = 1; i <= n;i++)
        ans = (ans + f[i] - 1) % mod;
    printf("%lld", ans * p[1] % mod);
    return 0;
}

I Incentive Model

题意：A、B两人争夺 $n$ 个区块，初始时二人获取一个块的概率为 $a,b$ ，满足 $a+b=1$ 。之后在第 $i$ 轮，每争夺到一个块，那个人获得 $w$ 的区块奖励（总池也增大 $w$ ），即他下一次获得区块的奖励变为 $\displaystyle \frac{a+(x+1)w}{a+b+wi}$ ，其中 $x$ 是他已经争夺到的块的数目， $w$ 为一给定常数。问 A 获得区块的期望个数。

解法：设 $S_i$ 为第 $i$ 轮结束后，A 获得的块数（含之前的块数），即 $a+wx$ 。这里 $S_i$ 可以写成一个分布列：

$S_i$	$a$	$a+w$	$a+2w$	$a+3w$	$\cdots$	$a+iw$
$p_{i,j}$	$p_{i,a}$	$p_{i,a+w}$	$p_{i,a+2w}$	$p_{i,a+3w}$	$\cdots$	$p_{i,a+iw}$

其中 $p_{i,j}$ 表示第 $i$ 轮 A 获得 $j$ 个块的概率。则容易写出， $\displaystyle E(S_i)=\sum_{j=a}^{a+iw} j p_{i,j}$ 。根据题意，不难写出一个递推： $\displaystyle p_{i+1,j}=\frac{a+b+wi-j+w}{a+b+wi}p_{i,j}+\frac{(j-w)p_{i,j-w}}{a+b+wi}$ 。

注意到 $E(S_0)=a$ 。考虑 $E(S_{i})$ 的递推。 $\displaystyle E(S_{i+1})=\sum_{j=a}^{a+(i+1)w}jp_{i+1,j}=\sum_{j=a}^{a+(i+1)w}j(\frac{a+b+wi-j+w}{a+b+wi}p_{i,j}+\frac{j-w}{a+b+wi}p_{i,j-w})$ 。将求和符号展开，利用 $j>a+wi$ 时 $p_{i,j}=0$ ，可以将后侧的 $j-w$ 用 $j$ 替换，得到 $\displaystyle \sum_{j=a}^{a+iw} \frac{a+b+wi-j+w}{a+b+wi}jp_{i,j}+\sum_{j=a}^{a+iw}\frac{j}{a+b+wi}jp_{i,j}=\sum_{j=a}^{a+iw}\frac{a+b+w+wi}{a+b+wi}jp_{i,j}=\frac{a+b+w+wi}{a+b+wi}E(S_i)$ 。因而得到 $\displaystyle E(S_i)(1+\frac{w}{1+wi})$ 。因而，可以写出 $E(S_i)$ 的通项公式： $\displaystyle E(S_i)=E(S_0)\prod_{j=0}^{i-1}\frac{1+(j+1)w}{1+jw}=a(1+wi)$ 。