阿里3.23笔试，笔试被虐惨了，借鉴别人写的代码，供大家参考

题目

1、从n个人中选择任意数量的人员组成一支队伍，然后从一支队伍中选出一位队长，不同的队长算不同的组合，问这样的组合的数量对10^9+7取模 。

数据范围：1 <= n <= 1000000000;

示例

输入：n = 2
输出：4
解释,(1),(2)(1,2),(2,1)四种，括号第一个为队长

思路:

首先一看数据范围，应该要O(logN)级别的方法才能AC,分析问题首先应该是个排列组合问题，得到通项公式为：
$$
思路1：可以暴力算，当然不推荐，算了也是白算

思路2：动态规划，没写出来，而且也达不到O(logN)复杂度

思路3：数学知识告诉我们，res的通项公式为：
$$
要求2^n - 1，O(logN)复杂度，经典的快速幂算法。

小知识：介绍一个解决找规律问题的好网站OEIS（ 在线整数数列查询网站 http://oeis.org/ ），笔试的时候手机被锁了，没想到用电脑去查一查，好气

import java.util.Scanner;

public class Main {
    static int mod = 1000000007;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        System.out.println((pow(n - 1) * n) % mod);
    }

    public static long pow(int n) {
        if (n == 0)
            return 1;
        long half = pow(n / 2);
        if (n % 2 == 0)
            return (half * half) % mod;
        else
            return (half * half * 2) % mod;
    }
}

2、 一个地图n*m，包含1个起点，1个终点，其他点包括可达点和不可达点。 每一次可以：上下左右移动，或使用1点能量从（i,j)瞬间移动到（n-1-i, m-1-j)，最多可以使用5点能量。

数据范围：2 <= n,m <= 500;

示例

输入：
4 4
#S..
E#..
....
....
输出：4
解释:S(0,1)先瞬移到(3, 2)，然后往上一步，往右一步，瞬移到E，一共4步

思路:

如果没有瞬移步数要求，那这就是一个经典的地图问题，算是BFS的模板题，那加入瞬移步数要求之后，需要记录fly变量，fly表示已经瞬移的步数。

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int [] dx = {1, -1, 0 ,0};
    static int [] dy = {0, 0, 1, -1};
    static int n;
    static int m;
    static int endX;
    static int endY;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        n = input.nextInt();
        m = input.nextInt();
        char[][] map = new char[n][m];
        Queue<Pair> queue = new LinkedList<Pair>();
        for (int i = 0;i < n;i++) {
            map[i] = input.next().toCharArray();
            for (int j = 0;j < map[i].length;j++) {
                if (map[i][j] == 'S') {
                    Pair pair = new Pair(i, j);
                    queue.add(pair);
                } else if (map[i][j] == 'E') {
                    endX = i;
                    endY = j;
                }
            }
        }
        System.out.println(BFS(map, queue));
    }
    public static boolean check(int x,int y) {
        if (x >= 0 && x < n && y >= 0 && y < m)
            return true;
        return false;
    }
    public static int BFS(char[][] map, Queue<Pair> queue) {
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                Pair top = queue.poll();
                if (top.x == endX && top.y == endY)
                    return top.step;
                for (int i = 0;i < 4;i++) {
                    int curX = top.x + dx[i];
                    int curY = top.y + dy[i];
                    Pair nextPair = new Pair(curX, curY);
                    nextPair.step = top.step + 1;
                    nextPair.fly = top.fly;
                    if (check(curX, curY) && (map[curX][curY] == '.' || map[curX][curY] == 'E')) {
                        queue.add(nextPair);
                        map[curX][curY] = 'X';
                    }
                }
                int flyX = n - 1 - top.x;
                int flyY = m - 1 - top.y;
                if (check(flyX, flyY) && top.fly < 5 && (map[flyX][flyY] == '.' || map[flyX][flyY] == 'E')) {
                    Pair pair = new Pair(flyX, flyY);
                    pair.step = top.step + 1;
                    pair.fly = top.fly + 1;
                    queue.add(pair);
                    map[flyX][flyY] = 'X';
                }
            }
        }
        return -1;
    }
}
class Pair {
    int x;
    int y;
    int step;
    int fly;
    public Pair(int x,int y) {
        // TODO Auto-generated constructor stub
        this.x = x;
        this.y = y;
    }
}