xiaoyaowudi's blog

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$

- 阅读全文 -

给定正整数 $n,m$，求 $n$ 个点的没有自环和重边的有标号有向图 $G$ 的个数，使得 $G$ 中每个点在至多一个环上，且不在任意一个环上的边的数量恰好为 $m$。答案对 $10^9+9$ 取模。

- 阅读全文 -

给定正整数 $n,m\le 2\times 10^5$，有一枚质地均匀的，$n$ 个面的骰子。对于 $i=1,2\dots m$ 分别求出，不断扔这个骰子，直到每一面都出现过，所需步数的 $i$ 次方的期望。模数 $998244353$。

- 阅读全文 -

给定 $n$ 个编号为 $1,2,\dots n$ 的初始为空的栈，同时给定一个值域为 $k\left(1\le k\le 2n-1\right)$ 的正整数序列 $\left\{a_n\right\}$。保证每种数的出现次数都是偶数。你可以进行若干次下列两种操作，要求最后每个栈和序列 $\left\{a_n\right\}$ 均为空，构造一种合法的操作序列。

1. 若 $\left\{a_n\right\}$ 非空，取出 $\left\{a_n\right\}$ 的第一个数 $a_1$ 并将其删去，同时任意选择一个栈 $t$，将 $k$ 插入 $t$ 的栈顶。此时，若栈 $t$ 栈顶两个数相同，则将其同时从栈 $t$ 中删去。

2. 选择两个非空的不同的栈 $i,j,i\neq j$，满足栈 $i,j$ 的栈底元素相同，则同时将 $i,j$ 的栈底的数删去。

多测，$n\le 300$，序列总长度 $\le 2\times 10^6$

- 阅读全文 -