xiaoyaowudi's blog

有三个变量，初始为 $a,b,c$，每次随机选择一个变量 $+1$，求出操作 $1,2,\cdots n$ 次后最大值的期望。$\bmod\;998244353$

- 阅读全文 -

大概是全网首篇中文题解？

- 阅读全文 -

给定 $n$ 个 $m$ 位二进制非负整数 $B_1,B_2,\cdots B_n$ 和一个 $m$ 位二进制整数 $X$，求 $\left\{1,2,\cdots X\right\}$ 有多少个子集 $S$ 满足 $B$ 是 $S$ 的一组基。且 $S$ 的秩为 $n$。答案对 $998244353$ 取模。

$n,m\le 2000$

- 阅读全文 -

GDKOI2023 D1T2 错排

给定 $T$ 组正整数 $n,m$，分别求有多少个 $1\sim n$ 的排列 $p$ 使得 $\forall 1\le i\le m,p_i\gt m$ 且 $\forall m\lt i\le n,p_i\neq i$，答案对 $998244353$ 取模。

$T,n,m\le 2\times 10^5$

LNOI2022 T3 盒

有 $n$ 个不同的盒子排成一排。在初始状态下，第 $i$ 个盒子放有 $a_i$ 个货物，总货物数量为 $S=\sum_{i=1}^na_i$。对于非负整数数组 $\left(b_1,b_2,\dots,b_n\right)$ 满足 $\sum_{i=1}^nb_i=S$，考察以下问题：

你想让第 $i$ 个盒子中拥有恰好 $b_i$ 个货物，为此你可以做如下操作若干次：对两个相邻的盒子，把其中一个盒子的恰好一个货物移动至另一个。对 $i,i+1\left(1\le i\lt n\right)$ 号盒子做一次操作的代价为 $w_i$。注意：将 $i$ 号盒子的一个货物移动到 $i+1$ 号盒子和将 $i+1$ 号盒子的一个货物移动到 $i$ 号盒子的代价都是 $w_i$。你需要保证在操作中不存在盒子中的货物数量是负数。

在以上问题下，定义从初始状态达到第 $i$ 个盒子拥有恰好 $b_i$ 个货物的状态的最小代价为 $val\left(b_1,b_2,\dots,b_n\right)$，你需要求出对所有满足 $\sum_{i=1}^nb_i=S$ 的非负整数数组 $\left(b_1,b_2,\dots,b_n\right)$，$val\left(b_1,b_2,\dots,b_n\right)$ 的和。输出这个答案对 $998244353$ 取模后的结果。

$T\le 5,n\le 5\times 10^5,S\le 2\times 10^6$

- 阅读全文 -