1、有$n$个人，编号1到$n$。将其平均分到$m$个房间中，每个房间$K$个人。现在知道每个房间编号最小的人的编号。对于给出的人$x$。问其可能在的房间有多少种？
思路：先假设其在某个房间，然后判断可行否。将按照编号从大到小每个房间依次考虑。大于这个房间最小编号的人都可以在这里，多了就存起来。
#include <string.h>
#include <stdio.h>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <map>
using namespace std;const int N=55;class FindingFriend {public:int find(int m,vector<int> a,int k) {sort(a.begin(),a.end());int n=a.size();for(int i=0;i<n;++i) {if(a[i]==k) return 1;}int b[1111];for(int i=0;i<n;++i) {if(i==n-1){b[i]=n*m-a[i];if(k>a[i]) --b[i];}else {b[i]=a[i+1]-a[i]-1;if(a[i]<k&&k<a[i+1]) --b[i];}}--m;int ans=0;for(int i=0;i<n;++i) if(k>a[i]) {int ok=1;int tot=0;++b[i];for(int j=n-1;j>=0;--j) {if(b[j]<m) {if(m-b[j]>tot) {ok=0; break;}tot-=m-b[j];}else if(b[j]>m) {if(i==j) {if(m==0) {ok=0; break;}}tot+=b[j]-m;}}if(ok) ++ans;--b[i];}return ans;}};
2、
思路：把$f$函数看做树的边。最后的$k$个节点是一个闭包，即对于这个闭包中的任意一个节点$x$,$f(x)$也属于这个闭包。那么首先从选出$k$个节点，$C_{n}^{k}$。这$k$个节点组成闭包的方案数设为$s(k)$。假设现在知道了$s(k-1)$，那么对于第$k$个节点来说，要么自己是一个闭包，要么跟前$k-1$是一个闭包，所以$s(k)=(k-1)*s(k-1)+s(k-1)=k*s(k-1)$，所以$s(k)=k!$。
那么现在对于剩下的$n-k$个节点需要最后连接到选出的$k$个节点上。这里把选出的$k$ 个节点看做一棵树的树根，其余的$n-k$个节点加上树根现在有$n-k+1$个节点。其余的$n-k$个节点最后要连接到树根上。现在枚举连上树根的节点有$i$个，那么这$i$个节点最后连接到$k$个节点的方案数为$k^{i}$。而对于整个树来说，考虑它的prefer编码，由于树根上连上了$i$个节点，那么树根在最后的长度为$(n-k+1)-2$的prufer序列中出现了$i-1$次，所以有$C_{n-k-1}^{i-1}$种放置的方式，对于prufer序列的其余$(n-k-1)-(i-1)$个位置，每个位置可以放的节点种类为$n-k$，所以有$(n-k)^{n-k-i}$。所以答案为$C_{n}^{k}*k!*\sum_{i=1}^{n-k}k^{i}*C_{n-k-1}^{i-1}*(n-k)^{n-k-i}$。后半部分可以简化。
$\sum_{i=1}^{n-k}k^{i}*C_{n-k-1}^{i-1}*(n-k)^{n-k-i}$
$=\sum_{i=1}^{N}k^{i}*C_{N-1}^{i-1}*N^{N-i}$
$=k*\sum_{i=0}^{N-1}C_{N-1}^{i}*k^{i}*N^{N-1-i}$
$=k*(N+k)^{N-1}$
$=k*n^{n-k-1}$
#include <string.h>
#include <stdio.h>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <map>
using namespace std;const int N=5005;
const int mod=1000000007;int C[N][N];long long exGcd(long long a,long long b,long long &x,long long &y)
{long long r,t;if(b==0){x=1;y=0;return a;}r=exGcd(b,a%b,x,y);t=x;x=y;y=t-a/b*y;return r;
}long long inverse(long long a,long long m)
{long long x,y;exGcd(a,m,x,y);return (m+x%m)%m;
}long long f(int n) {long long ans=1;for(int i=1;i<=n;++i) ans=ans*i%mod;return ans;
}class CrazyFunctions {public:int count(int n,int k) {long long ans=f(n)*inverse(f(k)*f(n-k)%mod,mod)%mod;for(int i=1;i<=k;++i) ans=ans*i%mod;if(k<n) {ans=ans*k%mod;for(int i=0;i<n-k-1;++i) ans=ans*n%mod;}return (int)ans;}};