首页 > 试题广场 >

牛牛排队

[编程题]牛牛排队

热度指数：2064 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛和他的小伙伴一共n个人参加冬令营，他们的教官要求他们排成一排，每个人都有固定的位置，但是牛牛和他的小伙伴有些马虎，所以总是不记得他们到底站在哪个位置，但是他们记得之前站在他们左部分和站在他们右部分的人的人数差的绝对值a_i，根据这些值，牛牛想知道他们到底有多少种不同的站法？（结果需要对1e9+7取模）

示例1

输入

3,[2,0,2]

输出

说明

可能的站法(1 2 3)， (3 2 1)

示例2

输入

3,[1,1,1]

输出

说明

不存在这样的站法

备注:

其中1<=n<=1000000, 0<=a_i<=1000000

算法知识视频讲解

Java

Fubuki_0v0

题不难，输出坑，中间计算用的变量记得用long

public int solve (int n, int[] a) {
// write code here
//如果n为奇数，中间人1种，其余人每人2种，但某人确定后，对应另一个位置的人也确定了，共2^((n-1)/2)种
//如果n为偶数，每人2种，但某人确定后，对应另一个位置的人也确定了，共2^(n/2)种
if(n==1) {
return a[0]==0 ? 1 : 0;
}
if(n==2) {
return a[0]==a[1]&&a[0]==1 ? 2 : 0;
}
Arrays.sort(a);
if(n%2!=0 && a[0]!=0) {
return 0;
}
int c = (n%2==0 ? 1 : 2);
for(int i=(n%2==0 ? 0 : 1)+1; i<n; i+=2) {
if(a[i-1]!=a[i] || a[i]!=c) {
return 0;
}
c+=2;
}

int m = n/2;
long r = 1;
long d = 2;
while(m>0) {
if(m%2==1) {
r *= d;
}
if(r > 1000000007) {
r = r % 1000000007;
}
d*=d;
if(d > 1000000007) {
d = d % 1000000007;
}
m = m>>1;
}
return (int)r;
}

编辑于 2020-07-04 19:53:16 回复(0)