返回信息流4.18百度在线笔试问题，毫无头绪，感觉各家笔试题排列组合类问题还不少。
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #95672同步于 2018/4/19
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】百度笔试，排队问题
huruisheng
2018/4/19镜像同步23 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
是的[ema1]所以连个n＝2时候的答案都不敢确定
【 在 lance6716 的大作中提到: 】
: 5个人可能站在一起或者2-3（3-2）这么站。如果是2-3这么站注意不要挨在一起？完了一加上这个不要挨在一起顿时就复杂了
: --
:
感觉可以先对每个国家5个人全排列（阶乘）一下然后相乘，接下来对每个国家的['5', '2-3']两种情况笛卡尔积，形成了一条团一条团的队员。如果是'5'，这个国家的团没有不合法情况，如果是'2-3'，两个团不能相邻，可以计算出仅有这个约束下有几次不合法。对于笛卡尔积的每行（例如'5', '5', '2-3', '5'）按照多事件并集公式（忘记正式名称是啥了）计算出结果。对笛卡尔积所有行结果求和，乘以前面若干5的阶乘的结果
【 在 huruisheng 的大作中提到: 】
: 是的所以连个n＝2时候的答案都不敢确定
: :
要用到广义容斥原理，公式推了我大半天，不过这里不能发图
public class FivePesonForNCountry {
static int[][] npk = new int[30][30];
static int[] factor = new int[100];
static int MOD = 1000000007;
private static int biggerNumWithSameDigits(int num) {
int a = num & (-num);
int b = num + a;
return b | ((num^b)/a) >> 2;
}
private static int nPickK(int n, int k) {
if (n < k || n < 0) return -1;
if (k == 0 || k == n) return 1;
if (k > n/2) k = n-k;
int start = (1 << k) - 1;
int end = (1 << n) - (1 << (n-k));
int res = 0;
for (int i = start; i <= end; i = biggerNumWithSameDigits(i)) {
++res;
}
return res;
}
private static int factorial(int n) {
if (factor[n] != 0) return factor[n];
if (n == 0 || n == 1) {
factor[n] = 1;
return 1;
}else {
factor[n] = n * factorial(n-1);
return factor[n];
}
}
private static long countWayforTwo(int n) {
long sum = 0;
for (int i = 0; i <= n; ++i) {
int signed = (i & 1) == 1 ? -1 : 1;
sum += nPickK(n,i)*signed*factorial(2*n-i)%MOD;
}
return sum%MOD;
}
private static long powerWithUnsignedInt(int base, int exponent){
if (exponent == 0) return 1;
if (exponent == 1) return base;
long result = powerWithUnsignedInt(base,exponent>>1);
result *= result;
if((exponent & 1)==1) result *= base;
return result;
}
public static void main(String[] args) {
int factor5 = factorial(5);
for (int i = 1; i < 5; ++i) {
long a = powerWithUnsignedInt(factor5,i)%MOD;
long b = countWayforTwo(i)%MOD;
long res = (a*b)%MOD;
System.out.println("input:"+i+"output:"+res);
}
}
}
输出如下
input:1output:120
input:2output:201600
input:3output:736128000
input:4output:616605133
【 在 w1252675615 的大作中提到: 】
: 输出如下
: input:1output:120
: input:2output:201600
: ...................
这是我代码的输出
def A(n):
return n*A(n-1) if n>0 else 1
def C(n,m):
return A(n)/(A(n-m)*A(m)) if m>0 else 1
def mod(n):
return n%1000000007
def queue(n):
sum = 0
for i in range(n+1):
sum = C(n,i)*A(n+i) - sum
k = pow(120,n)
return mod(mod(k)*mod(sum))
n = raw_input('input n:')
print queue(int(n))
答案和楼上一样 难道是我蒙对了？
楼主感兴趣的话我可以说一下原理，还挺简单的