1. 石子游戏 问题可以简单转化为最少能取出多少个数，使得异或和为 \(k\)。 显然答案是小于 \(log(A_i)\) 的，因为线性基已经可以拼出所有数了。 所以可以考虑枚举这个答案，然后就是 \(dp_{i,j}\) 表示用 \(i\) 个数能否拼出 \(j\)。 转移可以用 \(FWT\) 优化，暴力做就是两个 \(log\) 的，因为只需要一项所以手动 \(IFWT\) 可以做到一个 \(log\)。
  2. 函数 看到这题有点眼熟，是一道用 \(powerful \ number\) 来做的题。 \(powerful \ number\) 大概就是指每个质因子次数都 \(\geq 2\) 的数，可以计算出这样的数个数是根号级别的。 如果原函数为 \(f\)，构造一个积性函数 \(g\) 满足 \(g\) 函数只在 \(powerful \ number\) 处取值不为 $0$。 一个积性函数 \(h\) 满足前缀和易于计算，然后使得 \(f=g*h\)。 因为 \(f_p=g_p*h_1+g_1*h_p=g_p+h_p=h_p\)，所以 \(h\) 一般就是个满足质数处取值与 \(f\) 相同的多项式函数。 这样的话依次把 \(f_{p^2},f_{p^3}...\) 展开差不多就能得到 \(g\) 的表达式。 化一下 \(f\) 前缀和式子就发现，搜这个 \(powerful \ number\) 出来然后乘 \(h\) 的前缀和就好了。
  3. 画 首先不考虑边的限制，然后这道题的做法是给定若干个 \([0,r_i]\)，求异或和为 \(C\) 的方案数。 也是一道见过的题，然后一个比较优秀的 \(O(nlog)\) 的解决办法是这样的。 从高到低考虑每一位，此时满足每个数的高位全部贴紧限制，如果这一位上有一个数没有贴紧限制，那么这个数的低位就可以随便选来满足异或和为 \(C\)。 所以对于存在不贴紧限制的方案，写一个 \(dp_{i,0/1,0/1}\) 表示前 \(i\) 个数，是否存在不贴紧限制的数，当前异或和就解决了。 否则全部贴紧限制，可以直接进行下一位。 然后对于存在边的限制，一个暴力点的想法是钦定不满足条件的边集。 相当于是形成了若干个强制相等的连通块，然后就用一个子集反演。 然后用 \(DP\) 优化一下这个暴力钦定的过程，改为每次加入一个点集，然后顺便计算出每个点集联通的方案数即可。 因为这个 \(DP\) 要记录已经考虑的点集、已经考虑点集中存在的有效权值。转移还得再枚举超集，所以复杂度看起来很高。 其实有效的状态数并不多。考虑首先把点集按照 \(R_i\) 的大小排序，那么每次取的就是点集中编号最小的点。 把这样的编号最小的点染色为 $2$，已经考虑的点染色为 $1$，还没考虑的点染色为 $0$。 那么对于最靠右的 $2$，左侧只有 $1,2$，右侧只有 $0,1$，所以状态数是 \(O(n*2^n)\) 的。 总复杂度可以写为 \(\sum \limits_{i=1}^n 2^{i-1}\sum \limits_{j=0}^{n-i}\binom{n-i}{j}2^j=\sum \limits_{i=1}^n 2^{i-1}3^{n-i}\)。 把 $3^$ 拆成 $3n3{-i}$，然后用等比数列求和一下就可以发现总复杂度是 \(O(3^n)\) 的。 还有一个问题是如何压 $3^n$ 的状态， DC 大神告诉我们分别将二进制表示三进制化然后相加就好了。