Solutions

题目 有 $n$ 个正整数 $a_n$。现在有一个下标集合 $S$，初始时为空，你需要依次实现 $q$ 次操作： 每次操作会给定一个整数 $x(1\leq x\leq n)$，如果当前 $x$ 不在下标集合 $S$ 中，则在 $S$ 中加入 $x$，否则删去 $x$。 每次操作过后，你都需要计算下面这个式子的值： $$\sum_{i<j,i,j\in S}[\gcd(a_i,a_j)=1]$ …

Jayun 发布于 2022-10-17 15:08:31

00

题目大意 给定 $n$ 个数，求出选 $k$ 数的异或和之和，模 $998244353$。 分析 对于每一二进制位，肯定只有异或值为 $1$ 才有贡献，那么就枚举这一位上取 $1$ 的个数为 $x$，那么取 $0$ 的个数对应地就为 $k-x$，这一位的贡献就为 $\binom{\text{count}(1)}{x}\cdot\binom{\text{count}(0)}{k-x}$。 代码 co …

Jayun 发布于 2022-10-17 14:48:05

00

题目大意 删除最少数，使得数组最大子段和小于 $S$ 。 分析 $S<0$ 显然只统计小于 $S$ 的数的个数。 最大子段和是可以根据 $f_i=\max (f_{i-1},0)+1$ 达到 $\mathcal{O}(n)$ 扫的。尽量避免带修等问题，就考虑一边扫一边微调：当扫到正数时，当前最大子段和是否大于等于 $S$ ，是则删除若干最大值；当扫到负数时，需要若干个最小 …

Jayun 发布于 2022-10-07 07:26:41

00