2021-08-11 12:50 北京大学 C++

关注

牛客多校第四场题解

B Sample Game

题意：使用一个不等概率的 $[1,n]$ 随机数生成器，如果当前这一轮摇出来的数比之前摇出来的数都大或者等，游戏继续；否则终止游戏，其得分为轮数的平方。问得分的期望。

解法：如果游戏不结束，那么我们生成出来的序列一定形如： $1,1,\cdots,1,2,2,\cdots,2,3,3,\cdots,3,\cdots$ ，当然中间有些数可能不取。

那么我们可以考虑构造一个多项式函数（生成函数）来表示这个序列： $f(x)=(1+x+x^2+\cdots)(1+x+x^2+\cdots)\cdots(1+x+x^2+\cdots)$ ，共 $n$ 个大的乘法。对于第 $i$ 个括号，其内部 $x$ 的次方数表示第 $i$ 个数被选取了多少次。因而整个序列一定是这个多项式函数中每个括号里选一项出来组合而成的。这个函数中的 $x$ 表示了待选择的物品，但是在每个括号中这个 $x$ 含义不同——它们分别代表了 $1-n$ 中每一个数。

这个时候考虑 $f(x)$ 其对应的生成概率。那么容易得到， $p(x)=(1+p_1x+(p_1x)^2+(p_1x)^3+\cdots)(1+p_2x+(p_2x)^2+(p_2x)^3+\cdots)\cdots(1+p_nx+(p_nx)^2+(p_nx)^3+\cdots)$ 。考虑 $\displaystyle f(x)=\frac{1}{1-px}$ 的无穷级数展开，为 $\displaystyle \sum_{i=0}^{\infty} (px)^i$ ，那么对于每一括号内，都是到无穷的。因而原函数 $p(x)$ 可以被写作 $\displaystyle \prod_{i=1}^{n} \frac{1}{1-p_ix}$ 。

同时我们再对 $p(x)$ 再做一次无穷级数展开，考虑每一项前面系数的含义。 $\displaystyle p(x)=\sum_{i=0}^{\infty} a_ix^i$ ，如果按照刚刚对 $x$ 的定义，那么这里的 $x$ 可以被引申成为总共的数字个数——不再区分这个 $x$ 到底是 $1-n$ 中的多少。那么对于这样的 $x$ 定义， $a_i$ 可以被理解为拢共长度 $l$ 大于 $i$ 的概率，即 $P(l>i)$ 。

考虑最后的答案，为 $\displaystyle \sum_{i=0}^{\infty}(P(l>i)-P(l>i+1)) i^2$ 。对于无穷级数一个常用技巧就是结合相邻的两项。将 $P(x)$ 相同的两项结合，得到 $\displaystyle \sum_{i=0}^{\infty} P(l>i)((i+1)^2-i^2)=\sum_{i=0}^{\infty} P(l>i) (2i+1)$ 。

注意到含 $i$ 的项。先考虑 $p(x)$ 的无穷级数展开的形式。 $\displaystyle p(x)=\sum_{i=0}^{\infty} P(l>i) x^i$ ，求导后就可以得到 $i$ 和 $P(l>i)$ 相结合的项—— $p'(x)=\sum_{i=0}^{\infty} P(l>i) ix^{i-1}$ 。令 $x=1$ ，则有 $\displaystyle p'(1)=\sum_{i=0}^{\infty} iP(l>i)$ 。 $\displaystyle p(1)=\sum_{i=0}^{\infty} P(l>i)$ 。因而最后答案可以化简成为 $2p'(1)+p(1)$ 。

显然上面的问题不是无穷级数能解决的了，回到原来的 $p(x)$ ，对于累乘的形式考虑使用对数求导法。 $\displaystyle \ln p(x)=-\sum_{i=1}^{n} \ln (1-p_ix)$ ，因而 $\displaystyle p'(x)=p(x) \sum_{i=1}^{n} \frac{p_i}{1-p_ix}$ 。带入 $x=1$ 可得， $\displaystyle p(1)=\prod_{i=1}^{n} \frac{1}{1-p_i}$ ， $\displaystyle p'(1)=p(1) \sum_{i=1}^{n} \frac{p_i}{1-p_i}$ 。

总体时间复杂度仅 $O(n)$ 。

#include <cstdio>
#include <algorithm>
using namespace std;
const long long mod = 998244353LL;
long long power(long long a,long long x)
{
    long long ans = 1;
    a %= mod;
    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);
}
long long p[105], w[105], ip[105];
int main()
{
    int n;
    scanf("%d", &n);
    long long tot = 0;
    for (int i = 1; i <= n;i++)
    {
        scanf("%lld", &w[i]);
        tot = (tot + w[i]) % mod;
    }
    tot = inv(tot);
    for (int i = 1; i <= n;i++)
        p[i] = w[i] * tot % mod;
    for (int i = 1; i <= n;i++)
        ip[i] = inv(1 - p[i] + mod) % mod;
    long long ans = 1, sum = 0;
    for (int i = 1; i <= n;i++)
        ans = ans * ip[i] % mod;
    for (int i = 1;i<=n;i++)
        sum = (sum + p[i] * ip[i] % mod) % mod;
    printf("%lld", ans * (1 + 2ll * sum) % mod);
    return 0;
}

D Rebuild Tree

题意：给定一个有 $n$ 个节点的树，问删去 $k$ 条边后再连接 $k$ 条边，依旧形成一棵树的方案总数。

解法：首先考虑这个方案数是什么，再考虑怎么求。

首先，对一棵树删去 $k$ 条边，那么原树被分割成了 $k+1$ 条边。现在考虑如何连接依旧形成一棵树。

考虑使用 prufer 序列，一个使用长度为 $n-2$ ，每个数都在 $[1,n]$ 之间的序列来唯一表示一棵有 $n$ 个节点的树。如果我们将新连上的边的到着点（即父亲）节点的编号（不是所属的连通块的编号）记下来，组成这样的 prufer 序列，那么累计的 prufer 序列有 $n^{k-1}$ 种。因为现在考虑将一个大连通块想象成一个点，我们不会在一个连通块内连边，只会在不同连通块之间连边。这是到着点的情况。

对于出发点，那么显然一个连通块内每个点都可以连出去，连接到它的父亲去。因而总体答案可以写作 $\displaystyle n^{k-1} \sum \prod_{i} s_i$ ，其中 $s_i$ 为第 $i$ 个连通块的编号，答案要将每一种划分对应的方案数 $\displaystyle n^{k-1} \prod_{i} s_i$ 求和起来。

显然，后面这个东西依旧是不可求的。考虑一个镜像问题：将一棵树划分成 $k+1$ 个连通块，每个连通块各取一个点的方案总数。虽然这个问题并没有什么实质性变化，但是一个好处在于——它可以设计 DP 了。

令 $f[i][j][0/1]$ 表示以 $i$ 为子树的根，这个子树内已经被删除了 $j$ 条边，形成了 $j+1$ 个连通块，当前节点 $i$ 是否被选取代表一个连通块的总的方案总数。考虑从 $u$ 的每一个儿子 $v$ 转移：

$f'[u][k][0]=\sum_{i+j=k} f[u][i][0] (f[v][j][0]+f[v][j-1][1])$ $f'[u][k][1]=\sum_{i+j=k} (f[u][i][1]f[v][j][0]+f[u][i][0]f[v][j][1])+f[u][i][1]f[v][j-1][1]$

大体含义即：对于当前节点，如果决定不取，那么对于和当前节点不连通的子树，无条件合并；否则就要和取了子树顶点的子树切割开来；

如果要取，考虑和子树的关系，是否联通：如果和子树保持联通，子树取了子树根，那么当前节点就不取；如果子树没取树根，那么当前节点就要取根；如果和子树不保持联通，那么子树是否取根都无所谓了，当前节点必取。

总体时间复杂度 $O(nk)$ 。

#include<cstdio>
using namespace std;
const int N=50010;
const int mod=998244353;
struct node{
    int from,to;
}edge[2*N];
int n,m,i,j,k,first[N],nxt[2*N],u,v,f[N][110][2],w[N],g[N][110][2];
void addedge(int u,int v){
    edge[i].from=edge[i+n-1].to=u;edge[i].to=edge[i+n-1].from=v;nxt[i]=first[u];first[u]=i;nxt[i+n-1]=first[v];first[v]=i+n-1;
}
void add(int &x,long long y){
    x=(x+y)%mod;
}
void dfs(int u,int father){f[u][0][1]=f[u][0][0]=1;w[u]=1;
    for (int i=first[u],v;i;i=nxt[i]){v=edge[i].to;if (v!=father){dfs(v,u);
        for (int i=0;i<=min(m,w[u]);i++) g[u][i][0]=g[u][i][1]=0;
        for (int i=0;i<=min(m,w[u]);i++) if (f[u][i][0]||f[u][i][1]){
            for (int j=0;j<=min(m-i,w[v]);j++){
                add(g[u][i+j][0],(1LL*f[u][i][0]*f[v][j][0])%mod);
                if (j) add(g[u][i+j][0],1LL*f[u][i][0]*f[v][j-1][1]%mod);
                add(g[u][i+j][1],(1LL*f[u][i][1]*f[v][j][0]%mod+1LL*f[u][i][0]*f[v][j][1])%mod);
                if (j) add(g[u][i+j][1],1LL*f[u][i][1]*f[v][j-1][1]%mod);
            }

        }
        for (int i=0;i<=m;i++) f[u][i][0]=g[u][i][0],f[u][i][1]=g[u][i][1];w[u]+=w[v];
    }
    }
}
int main(){
    scanf("%d%d",&n,&m);for (i=1;i<=n-1;i++) scanf("%d%d",&u,&v),addedge(u,v);
    dfs(1,0);for (i=1;i<=m-1;i++) f[1][m][1]=1LL*f[1][m][1]*n%mod;printf("%d\n",f[1][m][1]);return 0;
}

E Tree Xor

题意：给定一棵 $n$ 个点的树，每个点权值 $w_i$ 有一个范围 $[l_i,r_i]$ ，并且已知树上每条边连接的两顶点的异或值，问拢共的点赋值方案数。

解法：注意到一个非常明显的结论——如果我给定一个点的权值，那么整棵树上每个点权值都一定唯一确定。基于这个性质，我们可以先不妨令 $w'_1=0$ ，以此算出整棵树上所有点的基础权值 $w'_i$ 。如果 $1$ 号点真正的权值为 $w_i$ ，由异或的性质可以得到，每个点真正的权值为 $w'_i \oplus w_i$ 。因而我们现在的问题被转化成为了只需要考虑 $1$ 号点的权值区间问题。

考虑每个点的限制条件。对于一个合法的 $1$ 号点权值 $w_1$ ，它需要满足的性质为 $\forall i \in [1,n]$ ， $l_i \leq w'_i \oplus w_1 \leq r_i$ 。

因而考虑每一个方程的解集，总的解集就是这 $n$ 个方程解集的交。对于一个限制条件 $l_i \leq w'_i \oplus x \leq r_i$ ，其合法区间一定是基于每一位确定的，因而部分连续。用 Trie 树模拟，可以得到一定是不超过 $\log w'_i$ 级别的连续区间。或者可以想象一个区间为 $[0,2^{30}-1]$ 的一个大线段树，按照线段树划分区间的方式，可以分成不超过 $\log w'_i$ 个区间。

这些区间的具体得到方式是根据 $w'_i$ 进行考虑的。对于一个连续区间长度为 $2^k$ 的区间，显然来说可行的区间长度应该为 $2^{k-1}$ 。因而抛弃下面的 $k-1$ 个二进制位，并进一位，只考虑上面的二进制位。显然这个时候异或单调性满足，直接考虑左右端点，将其与新的 $w'_i$ 异或即可。

此处总结一个技巧：

$x \oplus a \geq l \Leftrightarrow M-|x\oplus a| \leq M-l \Leftrightarrow x \oplus a \oplus M \leq M \oplus l$ 。

代码实现上可以更加简单化：

//找到对于第 i 位上 满足l^a>b 的区间方法
int x = (l >> i ^ 1) << i;
if((x^a)>b)
    ...

因而问题进一步的被转化成为了——给定数量级为 $O(n \log n)$ 个区间，求其中被 $n$ 个区间覆盖的解集。注意到，对于一个限制条件，其转化出来的 $\log n$ 个区间互不相交，因而想要被 $n$ 个区间交必然是被 $n$ 个限制条件交。

而这是一个非常常见的问题，可以考虑直接排序，最后 $O(n)$ 的从左向右扫描即可。记录端点，表示当前过此点后区间覆盖次数是否发生变化，遇到一个覆盖区间次数等于 $n$ 的区间，统计这段答案。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair<int, int>> interval;
void change(int left,int right,int start,int end,int byte,int value)
{
    if(start<=left && right<=end)
    {
        int nowleft = (left >> byte) << byte;//去掉下面的位，表示真正应当加入线段树的区间
        int nowright = (right >> byte) << byte;
        int nowvalue = (value >> byte) << byte;
        interval.push_back(make_pair(nowleft ^ nowvalue, 1));//差分数组，只记录开头结尾
        interval.push_back(make_pair((nowright ^ nowvalue) + (1 << byte), -1));
        return;
    }
    int mid = (left + right) >> 1;
    if(start<=mid)
        change(left, mid, start, end, byte - 1, value);
    if(end>mid)
        change(mid + 1, right, start, end, byte - 1, value);
}
struct line
{
    int from;
    int to;
    int w;
    int next;
};
struct line que[200005];
int w[100005], headers[100005];
int cnt;
void add(int from,int to,int w)
{
    cnt++;
    que[cnt].from = from;
    que[cnt].to = to;
    que[cnt].w = w;
    que[cnt].next = headers[from];
    headers[from] = cnt;
}
int left[100005], right[100005];
void dfs(int place,int father)
{
    for (int i = headers[place]; i;i=que[i].next)
        if(que[i].to!=father)
        {
            w[que[i].to] = w[place] ^ que[i].w;
            dfs(que[i].to, place);
        }
}
int main()
{
    int n, ans = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n;i++)
        scanf("%d%d", &left[i], &right[i]);
    for (int i = 1; i < n;i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    w[1] = 0;
    dfs(1, 1);
    for (int i = 1; i <= n;i++)
        change(0, (1 << 30) - 1, left[i], right[i], 30, w[i]);
    sort(interval.begin(), interval.end());
    int depth = 0;//覆盖深度
    for (int i = 0; i < interval.size();i++)
    {
        depth += interval[i].second;
        if(depth==n)
            if (i != interval.size())
                ans += interval[i + 1].first - interval[i].first;
    }
    printf("%d", ans);
    return 0;
}

G Product

题意：给定 $D$ ， $n$ 和 $k$ ，求出 $\displaystyle \sum_{a_i \geq 0,\sum a_i=D} \frac{D!}{\prod_{i=1}^{n} (a_i+k)!}$ 。

解法：首先根据指数型母函数，有结论： $\displaystyle \sum_{a_i \geq 0,\sum a_i=D} \prod_i \frac{D!}{a_i!}=n^D$ 。

考虑其证明：首先定义指数型母函数 $\displaystyle \prod_{i=1}^{n} \sum_{m \in M_i} \frac{x^m}{m!}$ 。这个式子表示了对于 $[1,n]$ 的数中，对每个数出现次数集合 $M_i$ 的母函数。对于指数型母函数，我们需要将其化成 $\displaystyle \sum_{i=1}^{\infty} b_i \frac{x^i}{i!}$ ，只有 $b_i$ 才对应了实际含义。

考虑回到上式，给定第 $i$ 个数出现次数为 $a_i$ ，那么其母函数为 $\displaystyle \prod_i \frac{x^{a_i}}{a_i!}$ 。由于 $\sum a_i=D$ ，因而原式后半部分可以化简为 $\displaystyle x^D \prod_i \frac{1}{a_i!}$ 。将其化为标准型，即 $\displaystyle (D! \prod_i \frac{1}{a_i!}) \frac{x^D}{D!}$ ，因而 $\displaystyle D! \prod_i \frac{1}{a_i!}$ 就是针对于一组 $\{ a_i \}$ 的方案数。

再考虑前面的求和符号，它遍历了全部划分方式， $1-n$ 中每个数可以随意出现。因而总的方案数等价于 $[1,D]$ 内的数，任取 $[1,n]$ 上的数的总方案数，即 $n^D$ 。

回到原题。题目即求 $D! \displaystyle \sum_{a_i \geq k,\sum a_i=D+nk} \frac{1}{\prod_{i=1}^{n} a_i!}$ 。如果完全无限制，即 $a_i \geq 0$ ，那么原式等于 $\displaystyle D! \frac{n^{D+nk}}{(D+nk)!}$ 。那么反过来考虑——将有违反 $a_i < k$ 性质的方案挖掉（容斥）即可。

考虑构建 DP： $f[x][y]$ 表示至少有 $x$ 个 $a_i<k$ ，且其总和为 $y$ 的 $\displaystyle\sum \frac{1}{\prod_{a_i<k} a_i!}$ 。此处仅考虑了这 $x$ 个数的问题。边界条件 $f[0][0]=1$ ，考虑其转移： $\displaystyle f[x][y]=\sum_{i=0}^{k-1} f[x-1][y-i] \frac{1}{i!}$ 。

递推完成后，考虑最后的容斥，只需要累加 $\displaystyle (-1)^x f[x][y] \dbinom{n}{x} \frac{(n-x)^{D+nk-y}}{(D+nk-y)!}D!$ 。后面的一项即是 $n-x$ 个满足 $a_i \geq 0$ ，和为 $D+nk-y$ 的 $\displaystyle \sum \frac{1}{\prod_{a_i\geq 0} a_i!}$ 。因为前面已经有违规的了，那么后面有违规的也无所谓了，都要加入被容斥的对象。

在实现上，考虑到 $\dbinom{n}{0}=1$ ，因而可以直接将最初的答案直接合并进这个操作中。

总体复杂度 $O((nk)^2)$ 。

#include <cstdio>
#include <algorithm>
using namespace std;
const long long mod = 998244353LL;
long long f[55][2505];
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);
}
long long fac[105], invfac[105], invp[2505];
long long C(int n,int m)
{
    if(n<m || m<0)
        return 0;
    return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
int main()
{
    int n, k;
    long long d;
    scanf("%d%d%lld", &n, &k, &d);
    long long ans = 0;
    invp[0] = 1;
    for (int i = 1; i <= n * k; i++)
        invp[i] = invp[i - 1] * inv(d + i) % mod;
    fac[0] = 1;
    for (int i = 1; i <= 100;i++)
        fac[i] = fac[i - 1] * i % mod;
    invfac[0] = 1;
    for (int i = 1; i <= 100;i++)
        invfac[i] = invfac[i - 1] * inv(i) % mod;
    f[0][0] = 1;
    for (int i = 1; i <= n;i++)
        for (int j = 0; j <= (i - 1) * (k - 1); j++)
            if(f[i-1][j])
                for (int l = 0; l < k;l++)
                    f[i][j + l] = (f[i][j + l] + f[i - 1][j] * invfac[l] % mod) % mod;
    for (int i = 0; i <= n;i++)
        for (int j = 0; j <= i * (k - 1); j++)
        {
            long long res = f[i][j];
            if(i%2==1)
                res = mod - res;
            res = res * C(n, i) % mod;
            res = res * power(n - i, d + n * k - j) % mod;
            res = res * in*** * k - j] % mod;
            ans = (ans + res) % mod;
        }
    printf("%lld", ans);
    return 0;
}

H Convolution

题意：定义运算 $\displaystyle x \oplus y=\prod_{i=1} p_i^{|a_i-b_i|}$ ，其中 $\displaystyle x=\prod_{i} p_i^{a_i}$ ， $\displaystyle y=\prod_{i} p_i^{b_i}$ 。给定序列 $\{a_i\}$ 和 $c$ ，求 $b_i=\sum_{1 \leq j,k \leq n, j \oplus k =i} a_j k^c$ 。

解法：首先由性质 $a+b-2\min{\{a,b\}}=|a-b|$ 可得， $\displaystyle x \oplus y=\frac{xy}{\gcd ^2{(x,y)}}=\frac{x}{\gcd(x,y)} \frac{y}{\gcd(x,y)}$ 。一个常见技巧是令 $x'=\frac{x}{\gcd(x,y)}$ ， $y'=\frac{y}{\gcd(x,y)}$ ，同时枚举 $d=\gcd(x,y)$ ，即可在 $O(n\log n)$ 的时间内遍历完所有的 $x,y$ 。因而 $x \oplus y=i$ 的条件可以转化为枚举 $\gcd(x',y')=1$ 和其原来的公约数 $d$ ，则 $i=d$ 。

$\displaystyle b_i=\sum_{1 \leq x',y'\leq n,\gcd(x',y')=1} \sum_{d=1}^{\lfloor \frac{n}{\max \{x',y' \}} \rfloor} a_{x'd} (y'd)^c$ ，此处将 $x=x'd,y=y'd$ 做替换。提出 $y'^c$ ，这样后面的求和与 $y'$ 就无关了—— $\displaystyle b_i=\sum_{1 \leq x',y'\leq n,\gcd(x',y')=1} y'^c \sum_{d=1}^{\lfloor \frac{n}{\max \{x',y' \}} \rfloor} a_{x'd} d^c$ 。

令 $m=\lfloor \frac{n}{\max \{x',y'\}} \rfloor$ ，将后面的求和符号提前预处理出来——令 $s_{x,m}=\sum_{d=1}^{m} a_{x'd} d^c$ 。这个预处理也是 $O(n \log n)$ 的。因而整个式子就可以在 $O(n \log n)$ 内完成了。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const long long mod = 998244353LL;
long long gcd(long long x,long long y)
{
    return y == 0 ? x : gcd(y, x % y);
}
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 po[1000005];
long long a[1000005], b[1000005];
int main()
{
    int n, c;
    scanf("%d%d", &n, &c);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for (int i = 1; i <= n;i++)
        po[i] = power(i, c);
    for (int i = 1; i <= n; i++)
    {
        vector<long long> sum(n / i + 1);
        for (int j = 1; j * i <= n;j++)
            sum[j] = (sum[j - 1] + a[j * i] * po[j] % mod) % mod;
        for (int j = 1; j <= n / i;j++)
            if(gcd(i,j)==1)
                b[i * j] = (b[i * j] + po[j] * sum[n / max(i, j)] % mod) % mod;
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++)
        ans ^= b[i];
    printf("%lld", ans);
    return 0;
}