Solutions

题意 定义一个无向图的权值为所有结点度数的 $k$ 次方之和（规定 $0^0=1$ ）。 求所有 $n$ 个点的简单无向图的权值之和。 答案对 998244353 取模。 $n\leq10^9,0\leq k\leq5\times10^5$ 。 题解 可以对于每个点的贡献然后乘 $n$ 。考虑每个点贡献的组合意义，相当于是 $k$ 个有标号点放进 $d$ 个有标号桶里，并且可 …

Jayun 发布于 2023-01-28 07:53:08

00

题意 给定一棵 $n$ 个点的有根树，其中 $1$ 号点是根，定义 $f(x)=\sum_{i\leq j,\mathrm{LCA}(i,j)=x}(w_i+w_j)$ 。 现在你需要支持两种操作： 1 x v：对于所有 $x$ 子树内和 $x$ 距离不超过 $2$ 的点 $y$ ，令 $w_y\leftarrow w_y+v$ 。 2 x：询问 $f(x)$ 的值。 …

Jayun 发布于 2023-01-28 07:52:57

00

题意 一个长度为 $n$ 的整数序列 $\{h_i\}$ ， $m$ 种操作，每种操作为花费一定的代价将一段长度为给定值的连续子区间加一或减一，每种操作都可以使用任意多次。 求把 $\{h_i\}$ 变成单调不降的最小代价，或者判断无解。 $n,m\leq200$ 。 思路 区间加一减一，用差分维护，设差分数组 $a_i=h_i-h_{i-1}$ 。那么目标就是要使所有 $a_i …

Jayun 发布于 2023-01-28 07:52:51

00

大意 给定长度为 $n$ 的系数数组 $a_i$ 和 $l,r$ ，求出长度为 $n$ 的数组 $x_i(x_i\in\mathbb{N})$ 使得： $$l\leq \sum_{i=1}^na_ix_i\leq r $$ 问 $x_i$ 数组有多少个。 $n\leq 12,1\leq l\leq r\leq 9\times10^{11},1\leq a_i\leq5\ti …

Jayun 发布于 2022-11-25 16:58:52

00

题目 阿申准备报名参加 GT 考试，准考证号为 $N$ 位数 $X_1,X_2,…,X_n$ ，他不希望准考证号上出现不吉利的数字。 他的不吉利数字 $A_1,A_2…A_m$ 有 $M$ 位，不出现是指 $X_1,X_2,…,X_n$ 中没有恰好一段等于 $A_1,A_2,…,A_m$ ， $A_1$ 和 $X_1$ 可以为 $0$ 。阿申想知道不出现不吉利数字的号码有 …

Jayun 发布于 2022-11-21 17:17:04

00

题目 给出一个长度为 $n$ 的 $k$ 进制数，可能含有前导 $0$，你需要实现以下 $4$ 种操作，共 $m$ 次。 1 x y：将第 $x$ 位上的数改为 $y$； 2 l r：将第 $l$ 位到第 $r$ 位升序排列； 3 l r：将第 $l$ 位到第 $r$ 位降序排列； 4 l r：求第 $l$ 位到第 $r$ 位所组成的 $k$ 进制数转为 $10$ 进制数的结果，结果对 $998 …

Jayun 发布于 2022-10-18 16:11:14

00

题目 城市中有一条长度为 $n$ 的道路，每隔 $1$ 的长度有一个公交车站，车站的编号从 $0$ 到 $n$，市政府在 $0$ 号车站的位置。 城市中同时有 $n$ 趟公交线路，第 $i$ 条公交线路的起点站为 $i-1$。公交车站 $i(0\leq i\leq n)$ 有两个属性 $c_i$ 和 $v_i$，代表从这个公交车站出发的公交车的性质。 $c_i$ 代表这个从 $i$ 出发的公交车， …

Jayun 发布于 2022-10-17 21:14:51

00

题目 有 $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