喜欢的话就坚持吧

分类目录
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)!}

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

11月 30

       二组小组互助

继续阅读

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

11月 02

继续阅读

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

10月 22

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

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

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

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

10月 13

给你m个数,分别为a_1,a_ 2…a_m求在模p意义下,n以内有多少数不能被k*a_i表示。(k\in N)
m<=50,n<=1e9

继续阅读

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

10月 12

题目大意

给了你一个序列a,每次查询给一个区间[l,r]
查询 l \leq i< j \leq r且a_i \oplus a_j的二进制表示下有k个1的二元组(i,j)的个数。\oplus是指按位异或。

对于5%的数据,为样例
对于30%的数据,1 \leq n , m \leq 5000
对于50%的数据,空间限制为512MB
对于100%的数据,1 \leq n , m \leq 100000 , 0 \leq ai , 2^k < 16384

继续阅读

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

10月 11

因为我最初讲莫队时没好好听,所以现在还是不会。

于是就有了本文,是一个初学莫队人的学习路程。
会根据博主学莫队的顺序更新。

继续阅读

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

10月 11

题目大意

点我看题)给你一颗树,每次使一个点(不)为关键点,你可以从任意一关键点出发,遍历所有点再回到出发点。对于每次操作,求最小路径。

继续阅读

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

10月 08

啊?da♂rk連鎖。
……原題省略。

題目大意:

給你一棵n個節點的樹,然後往樹上添m條非樹邊。
允許你砍掉一條樹邊和一條非樹邊
使這個圖形變成兩個連通塊。
問有多少種切發?

继续阅读

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

9月 22

考的真是垃圾,t2暴力写挂(其实离正解就差一点点),t3水题没时间写了。

这是noip考试,没有复杂数据结构。(noip2017day2t3了解下)

继续阅读

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。