12和13的noip中的问题...紧急解决【重要流程】。

将n个区别球放入m个相同的盒子中，不需要空盒子。不同方案的数目用S(n，m)表示，称为第二类斯特林数。

有n个不同的球，分别用B1，B2，...10亿从里面拿出一个球。有两种方法放置bn:

1)bn单独占一个箱子；那么剩下的球只能放在m-1的盒子里，方案数是S(n-1，m-1)。

2)bn等球占一个箱子；然后你可以把n-1的球B1，B2，...预先将bn-1放入m个盒子中，然后将球bn放入其中一个盒子中，方案数为m*S(n-1，m)。

S(n，m)=m*S(n-1，m)+S(n-1，m-1)(n & gt；1，m >1)

边界条件:S2 (n，1)= 1；S2(n，n)= 1；S2(n，k)=0(k >n)

2.289人

把n写成2的k次方加x的形式。

那么J[N]=2X+1。

400=2的8次方加上144。

所以是第2 * 144+1 = 289人。

3.取一个满足要求的子集A进行分析:

A={a1，a2，a3...安(n & gt=3)}

a1，a2，A3至少有两个人不认识。假设A1和A2不认识！

然后:A中只有一个人必须知道a1和a2！

在A，除了am大家都不知道a1和a2！

再看看，谁知道我是谁？明明a1和a2是认识的！

如果还有一个am1知道am，那么:am1不知道a1，不知道a2。

所以:知道am1和a1的A中一定有且只有一个am2！

另一方面，我们说A中除了am没有人知道a1和a2！

所以am1的假设不成立！

换句话说，知道am的只有a1和a2！

假设集合中的另一个元素am3显然不知道am。

那么很明显，根据(3)，集合中必须有一个人知道am和am3。

而我们说知道am的只有a1和a2！

所以我们假设的am3不成立！

所以a中只能有三个元素！{a1，a2，am}

但在这种情况下，am知道集合中的所有人，这不符合(1)。

所以这样的子集是不存在的！