给定 \(n,k,c\)，以及长度为 \(n\) 的序列 \(a\)（保证元素互不相同）。

操作 \(k\) 次，每次随机选择一个 \(a_i\)，然后将其 \(−1\)。

对于 \(x=0,1\dots2^c−1\) 输出最后序列的异或和为 \(x\) 的概率。

答案对 \(998244353\) 取模。

\(k,c\leqslant 16\)，\(a_i\in[k,2^c)\)，\(n\leqslant 2^c−k\)。

题目链接

这两道题是一个类型的，所以放到一起写了。

C - Triangular Relationship

如果 \(K\) 是奇数，那么一定有 \(K\mid a,K\mid b,K\mid c\)，所以答案为 \(\lfloor\frac{N}{K}\rfloor^3\)。

如果 \(K\) 是偶数，还有可能 \(a,b,c\equiv \frac{K}{2}\pmod K\)，所以在奇数的基础上还要加上 \(\left(\lfloor\frac{N-\frac{K}{2}}{K}\rfloor+1\right)^3\)，注意如果 \(N<\frac{K}{2}\) 时不能加上。

C - /\/\/\/

计算出 t1[] 和 t2[] 表示奇数和偶数位置上每个数出现的次数，枚举奇数位改成了哪一种数，那么偶数位就改成不等于这个数之外的出现最多的数，用前缀和后缀最大值解决。

题目链接

题目链接

美食家

我们很容易写出朴素的 dp 方程，设 \(f(i,u)\) 为第 \(i\) 天在城市 \(u\) 能得到的最大愉悦值之和，那么有转移： \[ f(i,u)=\max_{(v,u)\in E}f(i-w_{(v,u)},v)+c_u \]

求 \(k\) 进制下可以表示为纯循环小数（认为整数也是）的既约分数 \(\dfrac{i}{j}\)，且 \(1\leqslant i\leqslant n\)，\(1\leqslant j\leqslant m\) 的个数。\(n,m\leqslant 10^9\)，\(k\leqslant 2000\)。

A - Integer Product

由于每一个数都可以表示为十进制下的有限小数，所以化成分数后其分母的只可能含有 \(2\) 和 \(5\) 两个质因子。记录其次数，那么就是求 \(2\) 和 \(5\) 的次数加起来都大于等于 \(0\) 的数对个数。这个可以开一个桶暴力计算。

为了方便，一开始把每个数都乘上 \(10^9\)，这样求的就是次数加起来大于等于 \(18\) 的数对个数。复杂度 \(O(n\log^2n)\)。

代码