牛客网NC81-20.7.20(快速幂（））
【牛客网NC81-20.7.20(快速幂（））】题意：有n个人，排成一排，给一个数组a, a[i]代表第i个人左右两边的人的差值，问有多少种排法。
输入：人数n,差值数组a[] (1<=n<=1e6,0<=a[i]<=1e6)
输出：排法数mod(1e9+7)
分析：
若n为奇数：除了中间一个是0，以中间为分界，差值对称且是每次加2的偶数，例：6、4、2、0、2、4、6。
若n为偶数：以中间为分界，差值对称且是每次加2的奇数，例：5、3、1、1、3、5
本来除了n为奇数时中间一个人没得选，其他时候对于每个人来说都有两个位置选，所以有2(n/2)种选法。为什么不是2(n)种，因为差值相同的人确定了一个另一个也随之确定.
思路：对n==1特判，对a[i]的值检测是否符合标准。然后可以快速幂求2^(n/2)…好像也可以不用快速幂暴力求也能过
代码：`
import java.util.*;
public class Solution {
/**
*
* @param n int整型
* @param a int整型一维数组
* @return int整型
*/
static int maxn=(int)1e6+5;
static int Mod=(int)1e9+7;
public int solve (int n, int[] a) {
// write code here
int[] arr=new int[maxn];
for(int v:a)arr[v]++;
if(n%2==0){
for(int i=0;
i0){
if(hh%2==1)ans=ans*muti%Mod;
muti=muti*muti%Mod;
hh/=2;
}
return (int)ans;
}
}`
ps：又是摸鱼的一天
推荐阅读
- parallels|parallels desktop 解决网络初始化失败问题
- 猎杀IP
- 自媒体形势分析
- 数学大作战
- 使用协程爬取网页，计算网页数据大小
- 【亲测好用】高逼格配色网站推荐
- 2018.03.18
- 星期天的下午茶（一）
- 很多网红在用的素颜霜，你知道它是属于护肤品还是化妆品吗（）
- 08黑龙江迟淑荣弯柳树网络学院第五期学习赵宗瑞老师主讲的（传统文化与身心健康）教育体系心得体会