xiaoyaowudi's blog

证明:

$\displaystyle\sum_{k}\left\{\begin{matrix}n+1\\k+1\end{matrix}\right\}\binom{n-k}{m-k}\left(-1\right)^{m-k}k!=\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle$

- 阅读全文 -

证明:

$\displaystyle\sum_{j,k} (-1)^{j+k}\binom{j+k}{k+l}\binom{r}{j}\binom{n}{k}\binom{s+n-j-k}{m-j}=\left(-1\right)^l\binom{n+r}{n+l}\binom{s-r}{m-n-l}$

- 阅读全文 -

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$ 取模。

- 阅读全文 -