nowcoder_2024_1

A Bit More Common

有多少个长度为 \(n\) 的序列，值域范围 \([0,2^m)\)，满足至少存在两个不同的子序列并为 \(1\)。

如果是至少存在一个子序列，考虑用一个极长的合法子序列来映射一个序列。假设极长的合法子序列长度为 \(k\)，即只有这些第一位是 \(1\)，并且剩下的位不能全为 \(1\)。方案数是 \(\sum\limits_{i=1}^{n}\binom{n}{i}(2^{i}-1)^{m-1}2^{(n-i)(m-1)}\)

考虑恰好只有一个子序列合法的序列个数。同样枚举极长合法子序列的长度 \(k\)。只有一个合法子序列即不能删除其中任何一个数，也就是每一位都要拿到至少一个位，只有它在这一位是 \(0\)，否则的话一定可以删它。

枚举 \(t\) 个这样的特殊的位，这里也就相当于将 \(t\) 个有标号小球放入 \(k\) 个有标号的盒子，方案数是 \(\begin{Bmatrix}n\\m\end{Bmatrix}\times m!\) 。比赛的时候竟然没看出来这一步，真是离谱。当时想到是算不定方程所有解的多重集全排列，然而根本不会。

XOR of Suffix Sums

给一个操作序列。每次删除序列末尾的一些数字，求所有后缀和的异或值。

很妙的一个题，第一眼看到的时候，所有和的异或值，这东西没法拆位做啊。想了一下这个东西有点像去年杭电多校 2 的 1005，第 k 位的数字一定是连续模 \(2^{k+1}\) 之后不小于 \(2^k\) 的数字，然后就想到开 \(21\) 个权值线段树，每个树都相当于一个 \(modint\)，于是就可以查有多少个 1 了。考虑增加或者删除一个数字，也就是给这个线段树做一个循环位移，然而根本不知道怎么维护...

于是就一直卡 B，D 两题，也不开新题，为什么我总是拿不起放不下啊。

如果这题把后缀和改成前缀和我肯定就会做了，因为区间修改变成了单点修改。那么这个题是不是能转化为前缀和呢，\(suf_i=sum-pre_{i-1}\)，我们想知道 \(\mod 2^{k+1}\) 的那颗树有多少后缀和在 \([2^k,2^{k+1})\)，也就得到答案的第 \(k\) 位。

将 \(-pre_i\) 插入权值线段树中，查询多少个 \(x\) 满足 \(sum+x\mod 2^{k+1}\in[2^k,2^{k+1})\)。具体实现的时候是查询满足 \(2^k\le sum+x< 2^{k+1}\) 和 \(2^{k+1}+2^k\le sum+x< 2^{k+2}\) 的 \(x\) 个数。

2D Travel

有 \(k\) 个操作序列，在网格图上下左右移动，不能移出边界。有 \(q\) 个询问，问你从初始位置 \((x,y)\) 依次做了 \(l\) 到 \(r\) 的操作之后，停在哪个位置，移动了多少步。

因为都是给定操作，询问做一部分，无端联想到这个题（x：Even

比赛的时候队友在旁边搞莫队，本来以为很难。到最后压根没读过这个题...

首先两维是独立的，所以只用考虑一维情况。如果是一个无限大的网格，显然直接前缀和就行了。

我们定义做完了第 \(i\) 个操作之后如果停在边界，就称第 \(i\) 个操作为碰壁点。首先怎么快速找到从 \(l\) 开始的第一个碰壁点？也就是最小的 \(x\) 满足 \(pos+\sum_l^xa_i\ge n \vee pos+\sum_l^xa_i\le 0\)，前缀和之后可以解出 \(sum_x\) 对应需要满足的条件，这个东西可以用线段树二分或者 \(st\) 表预处理之后二分 \(O(logN)\) 求解。那么我们只用不断找碰壁点，然后处理边界就行了！

考虑加速这个过程，发现如果是碰撞点，那么人一定停留在边界位置，走到下一个碰撞点，仍然是在边界位置。如果有碰撞点的转移 \(A\rightarrow B, B\rightarrow C, C\rightarrow D, D\rightarrow E\)，实际上每个点的下一个碰撞点确定，连边也就成了一个森林，树上 \(k\) 级祖先显然可以用倍增做。具体来说，我们需要考虑从每个询问 \(i\) 开始，初始时在 \(0\) 和 \(n\) 的两种情况，走过 \(2^k\) 个碰撞点之后的状态分别用 \(f[i][k]\) 和 \(g[i][k]\) 。比如当前在 \(0\) 位置，操作 \(i\) 移动 \(0\) 步，那么 \(i\) 是碰撞点，\(f[i][0]=i+1\)。

大体思路就是这样，边界情况比较繁琐，懒得写了。