CSP 联训 2

觉得模拟赛题解还是单独放出来比较好。

A.挤压

好像不难？二进制表示下的平方展开没推出来，不然就成简单题了。

首先我们需要知道对于一个数 \(x\)，把它拆成 29 位的二进制形式后，用 \(s_i\) 表示二进制下第 \(i\) 位上的数，那么其实这个数就是 \((\overline{s_{29} s_{28}...s_1 s_0})_2\)，那么有

\[\begin{aligned} (\overline{s_{29} s_{28}...s_1 s_0})^2&=(\sum_{i=0}^{29} s_i\times 2^i)^2 \\ &=\sum_{i,j\in [0,29]} 2^{i+j} (if\ s_i=1\ and\ s_j=1)\end{aligned}\]

那么可以知道只有二进制下两位数同时为 1 时才会对答案有贡献，这样我们就可以枚举二进制下的两位 \(i,j\)，在此基础上循环整个序列设 \(f_{k,0/1,0/1}\) 表示前 \(k\) 个数的第 \(i,j\) 位选了奇/偶个的概率，最后计算上 \(f_{n,1,1}\) 对答案的贡献即可。

注意第 \(k\) 个数选或不选的转移有以下几种情况：

• 二进制下的这个数第 \(i,j\) 位都不为 1，那么显然它对答案，直接继承就行；

• 第 \(i\) 位为 1 而 第 \(j\) 位不为 1，那么若选这个数，则只有第 \(i\) 位的奇偶发生变化；反之同理；

• \(i,j\) 位都为 1，选这个数时，\(i,j\) 两位上的奇偶都发生变化，以此为例：

\[\begin{aligned}f_{k,x,y} &=f_{k-1,x\oplus 1,y\oplus 1}\times p_k (选这个数的概率) \\ &+f_{k-1,x,y}\times q_k(不选这个数的概率) \end{aligned}\]

对于每一组 \(i,j\)，初始化 \(f_{0,0,0}=0\) 即可。

B.工地难题

前缀和优化：设 \(f_i\) 表示最长连续 1 的个数 \(num\le i\) 的方案数，显然对于最长连续 1 的个数恰好等于 \(i\) 的答案就是 \(f_i-f_{i-1}\)。

现在我们考虑如何求 \(f_i\)。我们可以将题目理解为插板的形式：放好了 \(n-m\) 个 0，那么现在有 \(n-m+1\) 个位置可以插入 1，每个位置上都可以放 \([0,m]\) 个 1，问方案数。

设 \(x_j\) 表示第 \(j\) 个位置放了几个 1，那么求 \(f_i\) 其实就是求 \(\sum_{j=1}^{n-m+1} x_j=m\) 的非负整数解的个数。简单容斥一下就好了。