topcoder srm 700 div1 -3
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;
} };
最新文章
- excel基本
- 深入理解CSS中的层叠上下文和层叠顺序(转)
- [CLR via C#]25. 线程基础
- Java基础之创建窗口——使用卡片布局管理器(TryCardLayout)
- 安装软件配置VC++环境时常出现的问题--Error 1935.安装程序集
- Thread was being aborted.你遇到了吗?
- AngularJS+ASP.NET MVC+SignalR实现消息推送
- hardware_hp刀片服务器安装windows 2008系统配置
- Linux CentOS7 安装 Qt 5.9.2
- AOF持久化
- Servlet中的过滤器
- lch 儿童围棋课堂 启蒙篇 (李昌镐 著)
- Shell 编程(循环)
- Py designer 小程序实现实例
- async和await学习笔记
- Python2.7-datetime
- ThinkPHP 模型方法 setInc() 和 setDec() 使用详解
- 使用Nexus搭建Maven内部服务器
- kmeans聚类源代码
- Java(20~24)
热门文章
- hbase-java-api003(put list)
- 《大话设计模式》c++实现 建造者模式
- STL算法中函数对象和谓词
- Apache+Tomcat+Memcached实现会话保持
- 【Hadoop学习之六】MapReduce原理
- 联想拯救者win10+ubuntu14.04
- 用 hashcat 破解 WIFI WPA2破解
- 设计模式之Decorator(油漆工)(转)
- tornado 初识
- [转载]Java中的String,StringBuilder,StringBuffer三者的区别