可重组合与不相邻组合

发布于 # algorithm

可重组合

从 1,2,3⋯ ,n−1,n{1, 2, 3 \cdots, n - 1, n} 中选出 mm 个元素，可以重复，有多少个不同的组合？

答案 Cn+m−1mC_{n + m - 1}^{m}

证明

显然，问题可以转换为 mm 个球放入 nn 个盒子，可以放无数个或者不放

即插入 n−1n - 1 个隔板，然后求全排列 (m+n−1)!(m + n - 1)!

但是隔板和球的顺序是无效的所以除去 m!×(n−1)!m! \times (n-1)!

即

(m+n−1)!m!×(n−1)!=Cn+m−1m\frac{(m + n - 1)!}{m! \times (n - 1)!} = C_{n + m -1}^m

Prufer序列 入门 -- P2290 [HNOI2004]树的计数

发布于 # algorithm

0 前置知识点

1 Prufer 序列

对于一个带编号的无根树，其 Prufer 序列按以下过程处理

  1. 选取所有节点中度数最小编号最小的一个节点
  2. 输出其相邻的编号
  3. 回到 1 ，直到只剩两个节点为止

每个 Prufer 序列，都对应唯一的一个带编号的无根树

Luogu P2624 [HNOI2008]明明的烦恼

发布于 # algorithm

题目链接: https://www.luogu.org/problemnew/show/P2624

0 前置技能

1 推式子时间

这个题目很像 Luogu P2290

但是问题在于，这个里面具有不确定的度数

经过简单的思考，我们可以得出以下式子

Cn−2cnt×sum!∏i=1cnt(di−1)!×(n−cnt)n−sum−2C_{n - 2}^{cnt} \times \frac{sum!}{\prod_{i = 1}^{cnt} (d_i - 1)!} \times (n - cnt) ^{n - sum - 2}

其中

  • sumsum 为已知总度数
  • cntcnt 为已知点数

RSS 从入门到卸载客户端

发布于 # linux

0 说在之前

RSS 一说起这个词语，绝大多数人想到的都是 10 年以前，一行行字母，没有任何样式的网页，跟现今比起来，几乎没有任何的优势

故此我们总是觉得，RSS 已经成为了时代的眼泪，但是 RSS 的核心便是流，信息流，这和当下的媒体传播方式并无二，故只要运用得当，RSS 并不过气

Atom 上手指北

发布于 # linux

0 缘起

在 Luogu 日报上看到一篇 Atom小清新上手指南 ，经过了一番适应与调教，感觉十分优秀

不过多数这种自定义性极高的软件，通常都需要很多插件与一些配置，特写此文，留作自用

若能帮助到有需要的人，那是最好的

Woshiluo's NoteBook

「Jump up HIGH!!」