喜欢的话就坚持吧

1月 29

一些(无用)知识的补充

小r数学课又双叒叕走神了,他只记得老师在上课时讲了x1+x2+x3+x4=100等价与把小球装入盒子的方案数。但是小r忘了盒子是不是相同,球是不是相同,盒子能不能空?

于是他只好回家去问Seiga,作为小r的好朋友。Seiga耐心的帮小r辅导。

首先这个问题有3个变量:球,盒子,盒子是否可空。
所以我们可以写出下面8种情况:

1.将n个相同的球放入m个不同的盒中,可以空
\small f_{(n,m)}=C^n_{m+n−1}=\frac { (m+n−1)!}{n!(m−1)!}
解释:多重组合问题,就是从m个元素中可重复取n个不考虑顺序的方案。就是课上例题,考虑每个格子先放一个。

2.将n个相同的球放入m个不同的盒中,不能空,有多少种情况。
解释:课上例题 \small C^{n−m}_{n−1}=C^{m−1}_{n−1}

3.将n个相同的球放入m个相同的盒中,可以空。
Seiga:对于这个问题,需要用到母函数的知识,泰勒展开一下就好了,考虑到小r不会,就先放着。

不过这里给一个递推式:
设f(n,m)为n拆成m份的方案数。
如果这么拆:
\small x_1+x_2+x_3+…+x_m=n \tiny(x_i>=1)

\small x_1=1时,后面的拆法表示成f_{(n-1,m-1)}
\small x_1 \ge2时,式子可以变成\small (x_1-1)+(x_2-1)+…+(x_m-1)=n-m

所以后面的拆法表示成\small f(n-m,m)

所以f_{(n,m)}=f_{(n-1,m-1)}+f_{(n-m,m)}

4.将n个相同的球放入m个相同的盒中,不可以空
这个和上面的问题等价,会用到小r不会的知识,所以给出递推式:
自己想想
f(n,m)=f(n-m,m)+f(n,m-1)

5.将n个不同的球放入m个不同的盒中,可以空
果题:m^n

6.将n个不同的球放入m个不同的盒中,不可以空
\small \sum ^m_{i=0}(−1)^iC^i_m(m−i)^n
第二类Stirling然后全排列即可。
m!S(n,m)

小r:什么是第二类Stirling数?
Seiga:小r不急,我在下一章告诉你。
大力容斥也行。…式子不写了吧?

小r:Seiga,写一下式子吧…
Seiga:……

\small | \overline {A1}∩ \overline{A2}…∩ \overline {An}|=m^n−C^1_m(m−1)^n+C^2_m(m−2)^n+…+(−1)^mC^m_m(m−m)^n \newline \qquad\qquad\qquad\qquad \ \ =\ \small \sum ^m_{i=0}(−1)^iC^i_m(m−i)^n

7.将n个不同的球放入m个相同的盒中,可以空
因为可以有空盒,我们可以枚举每次一共用了几个盒子,然后把相应的第二类Stirling数加起来就可以了.
\sum ^m_{i=1}S(n,i)

Seiga:这个就是Bell数,我们记B(n)表示将集合{1,2,…,n}的划分数,就是将n个元素分为两两不交的子集,并集是全集。(就是此题题目的意思)。
详细的有些超纲,不赘述了。

8.将n个不同的球放入m个相同的盒中,不可以空
这就是刚才说的第二类Stirling数,
S(n,m)= \frac{1}{m!}∑^m_{i=0}(−1)^iC^i_m(m−i)^n
小r:这是怎么推倒的呢?
Seiga:至于证明…还是算了(才不是不会呢

听了Seiga的讲解,小r觉得自己快追上班里的平均水平了。…
于是…

题外话:由于有人建议要讲的难点,所以我写了点课上知识的拓(fei)展(hua)。
提示:这些可能在我下周出的简(du)单(liu)题要用。

n=2k+1
ans=\sum_{i=0}^{k-1} \frac{n!}{i!(i+1)!(k+1-i)!(k-1-i)!}+ \frac{n!}{i!(i+3)!(k-1-i)!(k-1-i)!}

阅读全文 >>

11月 05

题目大意

给你一张n个点,m条边的无向联通图,你从1号点出发,沿着边随意走动,走到n号点停止。走过边的价值为这条边的编号。让你给边从1~m标号,使价值的期望最大。

继续阅读

阅读全文 >>

10月 22

今天真是考了个假试,近一半的人ak。怕不是水题大赛

t1二分果题,t2搜索果题,t3 tarjan果题。

题解懒得写了,怕不是普及组都会做。

阅读全文 >>

10月 20

题目大意

农夫有一群奶牛,起初每头奶牛的奶产量是一定的。
农夫为了记录奶牛的奶产量,写了一个表格。表格有n行,每行有3个数表示分别表示日期(在整数1…10^6范围内),奶牛的编号(在整数1…10^9范围内),该奶牛的产奶量变化值。
为了鼓励奶牛的产奶,农夫会把产量最高的奶牛照片挂在墙上(奶量相同都挂),问根据记录的表格,推算出农夫移动照片的次数,(每次记录后如果移动多头奶牛的照片算一次,就是你记录后如果你重整照片,ans++)
n<=1e5

继续阅读

阅读全文 >>

10月 18

题目大意

给你一张n个点m条边的图,让你求出从1号节点出发到所有点的最短路,问不能选每条最短路到终点的前一条边时,1号点到所有点的最短路分别是多少?无解输出-1,保证原来的最短路唯一。
n<=100,000 m<=200,000;

继续阅读

阅读全文 >>