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;
} };