AMXOR

题意

简化后的题意：给定一堆数 $a_i$，求有多少组 $b_i\leq a_i$，使得 $\bigoplus_{i=1}^{n} b_i=0$，$n\leq 10^5, a_i\leq 2^{30}$（原题是异或值需要为给定的数）

分析

由于 $a$非常大，我们可能需要按位计算答案。

尝试如何将每一种可行的 ${b_i}$分类，以方便统计。根据上面的猜测，我们可能可以按位分类。

在数位 Dp 中常见的分类方法就是枚举某个数脱离上界的位置，这个问题中也可以。

我们枚举所有数中最早 (也就是更高位) 脱离上界的数是在第几位脱离上界 (即这个数的上限 $a$这一位为 1，而 $b$这一位为 0)，只要一个数在第 $k$位脱离了上界，更低的 $0\cdots k-1$位就可以随便填，即有 $2^{k}$种不同方案。对于剩下的还没有在第 $k$位脱离上界的数，它们的更低位可以随便填，只要不超过它们的上界就可以了，因为这些数的较低位异或出的数一定可以被最早脱离上界的数的较低位中和为 0。

实际上，这道题在实现上还是有很多细节的。

我们可以用 $f[k][i][0/1]$表示最早脱离上界的数在第 $k$位脱离上界，$\bigoplus b_1\cdots b_i$的第 $k$位为 $0/1$的方案数。

用 $c[k][i]$表示 $a[i]$的倒数 $k$位。

• 如果 $a_i$第 $k$位为 $0$：
  • $f[k][i][0]=f[k][i-1][0]\cdot (c[k-1][i]+1)$
  • $f[k][i][1] = f[k][i-1][1]\cdot(c[k-1][i]+1)$
• 如果 $a_i$第 $k$位为 $1$，我们可以枚举这个数是否脱离上界 (即这一位选 $0$还是 $1$)：
  • $f[k][i][0]=f[k][i-1][0]\cdot 2^k+f[k][i-1][1]\cdot(c[k-1][i]+1)$
  • $f[k][i][1]=f[k][i-1][1]\cdot 2^k+f[k][i-1][0]\cdot(c[k-1][i]+1)$

求出了这个，所有 “最早在第 $k$位脱离上界” 的情况总和就是 $f[k][n][0]/2^k$。

但是，对于某一个 $k$，没有任何一个数脱离上界也是有可能的，需要将这些情况减掉。

也有可能根本不存在 “最早在第 $k$位脱离上界” 的情况，因为有可能更高位的异或值根本就不是 $0$，这样不合法的情况也不能计算在答案内。

甚至有可能所有的数都不脱离上界仍旧是一个合法方案，因此答案可能需要最后加一。

Distinct Neighbours(CSA)

题意

给定一个序列，求有多少种这个序列的不同排列满足相邻两个元素不相同。序列长度不超过 $750$。实际上可以出到 $5000$，甚至 $10^5$。

分析

这类问题通常具有鲜明的状态。比如有多少个元素相邻就是一个状态。

因此我们可以依次向最终序列中添加每一种类型的元素，并且设 $f[i][j]$表示前 $i$种元素构成的有 $j$个元素相邻的排列的数量，假设前 $i$种元素一共有 $n$个，第 $i+1$种元素有 $m$个，那么，我们可以这样将 $f$转移：

首先，我们枚举前 $i$种元素共构成了几个相邻关系，再枚举第 $i+1$种元素拆开了几个前面的相邻关系，再枚举第 $i+1$种元素被拆分为了几段。这样：

设第 $i+1$种元素自身产生了 $t$个相邻关系，拆开了前面的 $l$个相邻关系，而前 $i$种元素构成了 $k$个相邻关系，则：
$$
f[i+1][k-l+t]=\sum_{k,l,t}f[i][k]\binom{m-1}{t}\binom{k}{l}\binom{n-k+1}{m-t-l}
$$
这样子的时间复杂度不会太低，总时间复杂度应该是是 $O((\sum n)^3)$，已经可以通过这道题。

实际上，我们还可以使用容斥原理。这里先证明一个结论，即多维容斥的成立性。
$$
\begin{aligned}
若：f[n][m] & =\sum_{i=0}^{n}\sum_{j=0}^{m}g[i][j]\binom{n}{i}\binom{m}{j}\\
则：g[n][m] & =\sum_{i=0}^{n}\sum_{j=0}^{m}f[i][j]\binom{n}{i}\binom{m}{j}(-1)^{n-i+m-j}\\
\end{aligned}
$$
证明：

$$
\begin{aligned}
f[n][m] & =\sum_{i=0}^{n}\binom{n}{i}(\sum_{j=0}^{m}g[i][j]\binom{m}{j})\\
由二项式反演：\sum_{j=0}^{m}g[n][j]\binom{m}{j} & =\sum_{i=0}^{n}f[i][m]\binom{n}{i}(-1)^{n-i}\\
g[n][m] &=\sum_{j=0}^{m}(\sum_{i=0}^{n}f[i][j]\binom{n}{i}(-1)^{n-i})\binom{m}{j}(-1)^{m-j}\\
& =\sum_{i=0}^{n}\sum_{j=0}^{m}f[i][j]\binom{n}{i}\binom{m}{j}(-1)^{n-i+m-j}
\end{aligned}
$$

实际上，更高维的容斥原理照样可以这样一层层运用二项式反演证明。

在本题中，我们令 $f$为 “可以有相邻的同色元素” 的排列个数，那么 $g$就是不存在相邻同色元素的排列个数。$f$是很好计算的，因此套用上述公式，我们可以在指数时间内得到 $g$。真是一个很大的优化呢。设 $f[a_1,a_2\cdots ,a_t]$表示在最终序列中，每一种球对应的连续段的个数分别为 $a_1,a_2\cdots ,a_t$的方案数。

但是，注意到这里的 $f$本身就是一个组合数，我们可以尝试将它拆开 (元素个数分别为 $n_i$)：
$$
g[n_1,n_2\cdots n_t]=\sum_{0\leq a_i\leq n_i}\frac{(\sum{a_i})!}{\prod (a_i!)}\prod \binom{n_i}{a_i}(-1)^{\sum{n_i}-\sum{a_i}}\\
=(-1)^{\sum n_i}\prod{(n_i!)}(\sum_{n=0}^{\sum n_i}n!(-1)^n\sum_{\sum{a_i}=n}\frac{1}{\prod{(a_i!^2(n_i-a_i)!)}})
$$
最后面那个大西格玛其实是一个卷积，是普通型生成函数 $\sum_{i=0}^{n}\frac{x^i}{i!^2(n-i)!}$的卷积，因此我们很容易求出这个魔鬼一样的函数的值，而且很快。就算我们不使用 $FFT$，也可以做到 $O(n^2)$。

实际上，还有一种更自然，但是需要去意会的推导方法，可以得出相同的结论。

我们直接定义一种类型的元素的 “带容斥系数的指数型生成函数” 为：
$$
F(x)=\sum_{i=1}^{n}\binom{n-1}{i-1}(-1)^{n-i}\frac{x^i}{i!}
$$
那么所有 $F(x)$的卷积就是答案。仔细一想，这样的几个 $F$的卷积，实际上在帮我们一层层套用二项式反演，从而最后 $\prod F$的各项系数之和就是我们所求的答案。

此外，这样的方法还有推广，比如 [JSOI2019] 神经网络一题也可以使用类似的方法。

Randomly Permuted Costs(CSA)

题意

给定一个可能存在重边和自环的 DAG，每到一个节点，所有出边的权值会随机打乱，你可以根据打乱后的权值选择合适的一条边前往下一个节点，或者走自环回到当前节点。求从 $s$到 $t$的期望最小花费。点数和边数在 $10^3$级别。

分析

一道让人耳目一新的题。类似的题还有 Intergalaxy Trips(CF605E)，只不过那一道题没有隐藏地这么深的技巧。

先考虑一下如果没有自环和重边可以如何处理这个问题。

事情是这样的，到达一个节点的时候，假设我们已经算出所有它的出边连向的节点的期望权值，则这些权值和每条出边的权值会被随机匹配，我们可以选择权值最小的一对匹配，前往那个节点。

因此，我们可以考虑求出每一对匹配作为最小权匹配的概率。这个好像不是很好求，因为 “最小” 意味着别人都比它小。但是我们可以求出所有匹配的权值都大于某个数的概率。

我们需要先将所有出边排序，所有点也排序。假设我们从小到大枚举这个权值。那么每条出边可以匹配的点的集合是单调变小的。假设某个时刻第 $i$条边可以匹配的点的集合为 $s_i$，那么所求的概率此时就是 $\prod\frac{|s_i|-i+1}{i}$。我们记录下每条边的匹配点集合变小的所有时刻，排序后顺次统计即可。

这样，我们就可以 $O(n^2\log n)$求出一个点的期望，总时间复杂度也是 $O(n^2\log n)$的。

但是，原题还有重边和自环。重边很好处理，只需要将边和点复制一遍即可，自环很麻烦。

那么我们就二分这个点的答案，将自己作为一个新的点，自环作为一条出边，重新算出这个点的答案，与二分的答案比较。

这样，我们就在 $O(n^2\log n\log X)$的时间内完成了求解。

在这里还有几个技巧

• 二分后计算出的新的答案是可以利用的。如果新的答案比二分的答案大，那么真实的答案一定比新的答案还大，因此直接将二分的左边界设为新的答案即可。右边界同理。
• 不需要每次将 “匹配点集合变小” 的时刻排序，而是事先排好序，将时间复杂度降低至 $O(n^2\log X)$。但是自环所代表的边的那些时刻会发生变化，此时只需要将变化之后的序列和没有发生变化的序列排序即可。

Set And Set (TopCoder12004)

题意：

给定一堆数字，将他们分为两组，使得两组的与值相同。求方案数。数字个数不超过 $50$，数字在 $[0,1048575]$内。

分析：

对于某一位，如果第一组内的数字这一位都是 1，另一组存在 0，这种分配方式是不合法的。反之是合法的。

这提示我们从不合法的方案入手，最终拿总方案减去不合法的。

于是，我们可以容斥。我们枚举问题出在哪几位，统计至少这几位有问题的分配方案数，然后容斥得到答案。

至少一些位有问题的分配方案数可以这样统计：由于出现问题的位为 0 的数全部得被分配到同一组，我们就可以用并查集将它们连在一起。最后根据联通块的个数得到这种情况下的分配方案数。

最后用到的容斥是一个简单的二项式反演的特例，即只需要求 $f[0]$。容斥系数只有 $+1$和 $-1$。

Cows Mooing (TopCoder12083)

题意：

给你一堆牛，牛不超过 $50$个，每头牛按照一个序列鸣叫，循环往复。对于 $i\in[1,50]$求 $1$到 $50!$秒内有多少秒有 $i$头牛一起鸣叫。

分析：

初看感觉非常简单，似乎根据中国剩余定理，每头牛鸣叫序列中任取一个时间，都能在 $50!$内找到唯一的一个时刻，这些牛都在执行各自序列中的那一位。

但是中国剩余定理基于模数两两互质的情况，在这里失效了。

由于我们需要处理模数不互质的情况，我们先考虑两头序列长度不互质的牛共同鸣叫的时刻如何计算。

假设两头牛的序列长度分别为 $a,b$，且 $\gcd(a,b)=g$，那么在 $\frac{ab}{g}$的时间内，存在一个时刻 $t$使得两头牛分别在执行各自序列的第 $x,y$项，当且仅当 $x\equiv y\pmod g$。这个不难证明。因此，如果我们需要处理模数不互质的情况，我们必须将两个序列分为 $g$组分别计算。

但是如果我们试图同时计算三头牛或者更多牛的答案，情况就变得复杂了。但是，如果我们可以知道一群牛两两之间的 $gcd$是相同的，我们还是可以按照两头牛的做法合并。更进一步，如果一群牛两两 $gcd$不同，我们依旧可以将它们的序列全部倍增至他们的 $lcm​$这么长，接着就可以按两头牛的做法直接统计。

由于牛比较多，我们显然不能把它们都倍增到一个很长的长度，我们就需要两种方法的结合：

因此，我们有了这样的一个思路：将牛分为若干组，每一组内的牛倍增到组内 $lcm$的长度；不同组间的牛的 $gcd$相同且很小。

如何划分呢？我们可以将所有最大质因子较小的牛全部放到一组，剩下的牛，按照最大质因子分组。

比如，我们将只含有 $2,3,5,7$的牛分为一组，合并之后发现，组内 $lcm$的长度为 $1058400$，可以接受。剩下的数，组内 $lcm$分别设为 $p_i\times 6$，这样就保证了上面提到的两个性质。

然后，将这每一组内的牛全部挤压成一头代表这个组的牛，这头牛每一秒可以鸣叫多次，然后我们合并这些 “组牛” 即可。

合并 “组牛” 的办法实际上就是按统计两头牛的方法统计，因为我们已经事先保证了任意两头 “组牛” 的 $gcd$都是 $6$。

Distance Graph (TopCoder12194)

题意：

给你一个 $m\leq 50$个点的无向图，给他们编上 $n\leq 100$以内的号码，号码不能重复。使得图中任意一条边连接的节点编号之差不大于 $d\leq 8$，补图中任意一条边连接的节点编号之差大于 $d \leq 8$。求编号方案数。

分析：

假设我们已经给节点赋予了合法的编号，并且将所有节点按照编号排好了序。

现在任意一个节点 $v$一定只会跟它的相邻节点连边。

也就是说，跟排名第一的节点连边的节点一定是排名前几的。

假设 $a,b$与排名第一的节点都有边，那么 $a,b$的大小关系直接与各自向后连边的条数相关。

如果 $back(a)<back(b)$，($back()$表示向后连边的条数)，那么 $a<b$，如果 $back(a)=back(b)$，$a$和 $b$谁都可以排第二。

这样以此类推，我们知道：如果确定了排名第一的节点是谁，整个序列就可以确定。

这样，我们可以：1. 枚举第一个节点。2. 确定一个序列。3. 判断这个序列是否合法。4. 通过状态压缩 Dp 求出这个序列的编号方案数。

本题得到了解决。

The Programming Competitions (TopCoder12183)

题意：

给你 $n\leq 50$支队伍，每个队伍有 $4$个人，$a_i\leq 4$个礼物。每支队伍需要将自己的礼物全部送给其他队伍的某些人，一个人最多得到一个礼物。求分配方案数。(人和礼物都是互不相同的)

分析：

存在一种 $O(n^2)$的 $dp$，因此 $n$可以大到 $10^3$这个数量级。

如果设 $f[i][j]$表示前 $i$组队伍，有 $j$个人已经得到了礼物的分配方案数，那么根据 $i,j$，我们就可以算出还剩下多少礼物没有分配。这样就可以通过两个变量清晰地、完整地描述每一个状态。

然后只需要枚举当前队伍将多少礼物送给前面，拿前面多少礼物，即可转移。

Yet Another Nim (Topcoder12149)

题意：

有 $n\leq 10^9$堆石子，每堆石子数量在 $[1,2^m)(m\leq 100)$内。$Alice$首先确定每堆石子的数量，$Bob$选择连续的 $k$堆石子。$Alice$将 $k$堆石子保留若干堆进行游戏。$Bob$先手开始 $Nim$游戏。求 $Alice$有几种必胜的摆放石子的方式。

分析：

如果任意连续的 $k$堆都是线性相关的，$Alice​$就可以赢。

那么设 $f[i][j]​$表示前 $i​$堆石子中后 $j​$堆线性相关的方案数，那么可以用一个不变的矩阵将 $f[i]​$转移到 $f[j]​$。另外，我们规定 $f[i][k]​$只能转移到 $f[i+1][k]​$，这样最终的 $f[n][k]​$就是 “存在” 连续 $k​$堆线性无关，这个状态下 $Alice​$输，反之都是 $Alice​$赢。

String Sequences (TopCoder12192)

题意：

给定两个字符串 $A,B$，求存在多少字符串序列 $A,s_1,s_2,\cdots,B$使得前一项通过插入一个字符都可以得到后一项。$|B|\leq 50$

分析：

为了避免重复计算这样的字符串序列，我们可以强行制定这样一个规则：如果存在连续一段字符 $c$，再次插入 $c$只能插在这一段的最左侧。

这样，我们可以尝试用这个规则算出 $B$的每一个子串对应多少种从空串插入字符的方案。

假设我们现在计算子串 $S$的生成方案，考虑第一个字符对应的位置 $p$, 那么 $p$前面是一个子问题，$p$后面是一个不能在最前面插 $S_p$的子问题。这样就将原问题划分为了两个形式相似的子问题。

最后再求一次两个字符串的每一种匹配对应的方案数之和。也可以通过 $Dp$求。

Even Paths (TopCoder11895)

题意：

给定一个 $DAG$，$DAG$上有 $m\leq 32$个关键点。可以在关键点设置障碍使得无法通行。求有多少种设置障碍的方式使得 $0-1$之间存在偶数条路径。$DAG$不超过 $50$个点，$500$条边。

分析：

可以考虑中途相遇。利用拓扑排序将 $DAG$切成两半。分别枚举两边关键点的选择情况，求出两边到分界线的路径的奇偶性。

但是分界线可能很长，不好合并。

因此我们从另一个方向考虑问题。对于每一条路径，我们在什么时候计算它呢？可以在这条路径碰到的第一个右侧关键点或者 1 好点处计算。这样，我们算出 $0,1$号点到右侧每个关键点的路径奇偶性，然后用 $FWT$就可以合并出答案了。