一、2n皇后

问题描述 给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。

输入格式 输入的第一行为一个整数n，表示棋盘的大小。 接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。

输出格式 输出一个整数，表示总共有多少种放法。

样例输入： 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

样例输出： 2

样例输入： 4 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1

样例输出： 0

思路：基本思路和8皇后相同，不同之处在于情况不仅是位置不同决定的，同一个位置不同颜色的棋子还有不同的结果。为了分区分，用2代表白皇后占的位置，用3代表黑皇后占的位置。我们规定先放白皇后，首先检查是否为1，如果不为1则该位置不可放置，continue检查下一个位置。如果可放，检查是否符合约束函数check()；如果不符合，continue检查下一个位置。如果符合，本行放置结束，执行putQueen(m+1, queen)递归下一行。同时注意回溯。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.util.Scanner;  

public class Main {
    static int  n;
    static int[][] chess;
    static int count = 0;
    public static void main(String[] args) {  
        Scanner in = new Scanner(System.in);  
        n = in.nextInt();  
        chess = new int[n][n];
  
        for (int i = 0; i < n; i++) {  
            for (int j = 0; j < n; j++) {  
                chess[i][j] = in.nextInt();  
            }
        }
        // 白皇后记为2，黑皇后记为3，先放白皇后       
        putQueen(0, 2);  
        System.out.println(count);  
  
    }  
    public static void putQueen(int m, int queen) {  
        if (m > n - 1) {  
        	if (queen == 2) {
        		putQueen(0, 3);
        	} else {
				count++;
			}   
            return;  
        }  
  
        for (int i = 0; i < n; i++) {
        	// 如果位置为0或者queen已放置，则不能放置
            if (chess[m][i] ！= 1) {
            	continue;
            }
            // 如果可放，则记录;反之，检查下一列           
            if (check(m, i, queen)) {  
                chess[m][i] = queen;
            }   else {
				continue;
			}
            // 继续判断下一行           
            putQueen(m + 1, queen);
            // 回溯，这里不用考虑0的位置，因为在上面已经被筛掉了，非常巧妙           
            chess[m][i] = 1;
        }  
    }  
    
    public static boolean check(int row, int col, int queen) {  
        int step = 1;
        while(row - step >= 0){
            if(chess[row-step][col] == queen) {                //上
                return false;
            }
            if(col-step >= 0 && chess[row-step][col-step] == queen) {       //左上
                return false;
            }
            if(col+step < n && chess[row-step][col+step] == queen) {       //右上
                return false;
            }
            step++;
        }
        return true;  
    }
}

二、分糖果（模拟）

问题描述 有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果，然后进行下面的游戏： 每个小朋友都把自己的糖果分一半给左手边的孩子。 一轮分糖后，拥有奇数颗糖的孩子由老师补给1个糖果，从而变成偶数。 反复进行这个游戏，直到所有小朋友的糖果数都相同为止。 你的任务是预测在已知的初始糖果情形下，老师一共需要补发多少个糖果。

输入格式 程序首先读入一个整数N (2< N <100)，表示小朋友的人数。 接着是一行用空格分开的N个偶数（每个偶数不大于1000，不小于2） 输出格式 要求程序输出一个整数，表示老师需要补发的糖果数。

样例输入 3 2 2 4 样例输出 4

解析：简单模拟即可，一开始没注意到最后一个不能直接同a[0]进行处理，因为前面的移动已经改变了a[0]的初始值，所以要多一步处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Main {
	static int n;
	static int[] a;
	static int cnt = 0;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		a = new int[n + 1];
		for (int i = 0; i < n; i++) {
			a[i] = in.nextInt();
		}
		while (true) {
			int j = 0;
			for (j = 1; j < n; j++) {
				if (a[0] != a[j]) {
					break;
				}
			}
			if (j == n) {
				break;
			}
			int x = a[0];
			for (int i = 0; i < n-1; i++) {
				a[i] = (a[i] + a[i+1]) / 2;
			}
			a[n-1] = (a[n-1] + x) / 2;
			
			for (int i = 0; i < n; i++) {
				if (a[i] % 2 != 0) {
					a[i] += 1;
					cnt++;
				}
			}
		}
		System.out.println(cnt);
	}
}

三、斐波那契（矩阵快速幂） 斐波那契数列大家都非常熟悉。它的定义是：

f(x) = 1 .... (x=1,2) f(x) = f(x-1) + f(x-2) .... (x>2)

对于给定的整数 n 和 m，我们希望求出： f(1) + f(2) + ... + f(n) 的值。但这个值可能非常大，所以我们把它对 f(m) 取模。 公式如下 这里写图片描述 但这个数字依然很大，所以需要再对 p 求模。 输入格式 　　输入为一行用空格分开的整数 n m p (0 < n, m, p < 10^18) 输出格式 　　输出为1个整数，表示答案 样例输入 2 3 5 样例输出 0 样例输入 15 11 29 样例输出 25 解析：数据量超大，需要用到大数处理，在求解斐波那契数列的时候要用矩阵快速幂的方法，下面的代码只能的40分，具体原因是在求f(1) + f(2) + ... + f(n)的时候没有处理好，做循环的时候不能用long n做上界，的确可以改成大数进行循环，但是这又牵扯到大数进行位运算，这里不是很明白，所以也无法给出满分的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static BigInteger[][] ZERO = {{BigInteger.ZERO,BigInteger.ZERO}, {BigInteger.ZERO,BigInteger.ZERO}};
    public static BigInteger[][] KEY = {{BigInteger.ONE,BigInteger.ONE}, {BigInteger.ONE,BigInteger.ZERO}};
    public static BigInteger MOD;
    
    public static BigInteger[][] mergeMulti(long n) {
        if(n == 0) {
        	return ZERO;
        }
        if(n == 1) {
        	return KEY;
        }
        if((n&1) == 0) {  // n为偶数
            BigInteger[][] temp = mergeMulti(n>>1);
            return matrixMulti(temp, temp);
        } else {  // n为奇数
			BigInteger[][] temp = mergeMulti(n>>1);
        return matrixMulti(matrixMulti(temp, temp), KEY);
		}
    }
    
    public static BigInteger[][] matrixMulti(BigInteger[][] A, BigInteger[][] B) {
        BigInteger[][] result = new BigInteger[A.length][B[0].length];

        for(int i = 0;i < A.length;i++) {
        	for(int j = 0;j < B[0].length;j++) {
        		result[i][j] = BigInteger.ZERO;
            	for(int k = 0;k < A[0].length;k++) {
                	result[i][j] = result[i][j].add(A[i][k].multiply(B[k][j]));
                }
            }
        }       
        return result;
    }
    
    public static BigInteger sum(long n) {
    	BigInteger cnt = BigInteger.ZERO;
        for (int i = 1; i <= n; i++) {
			cnt = cnt.add(mergeMulti(i)[0][1]);
		}
        return cnt;
    }
    
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long m = in.nextLong();
        MOD = in.nextBigInteger();
        BigInteger result = sum(n);
        result = result.mod(mergeMulti(m)[0][1]).mod(MOD);
        System.out.println(result);
    }
}