K-进制数 （Java代码）排列组合方法

解题思路:
对于N位的K进制数，若想不包含2个连续0的话，可以有如下几种情况：

①不含0：(K-1)^N个

②含1个0：由于最高位不能为0，所以有(N-1)*(K-1)^N-1个

③含2个0：相当于从一个(N-2)位不含0的数中插入2个0(最高位之前不插)，有C(n-2,2)*(K-1)^N-2个

......

④含i个0(i<=N/2)：相当于从一个(N-i)位不含0的数中插入i个0(最高位之前不插)，有C(n-i,i)*(K-1)^N-i个

以上各项求和即可得到答案，即Σ_(i:0→N/2)(K-1)^N-i

注意事项:

参考代码:

import java.util.Scanner;

public class T1117 {
	static int[][] dp = new int[18][18];
	public static int f(int n, int i) {
		if (dp[n][i] != 0)
			return dp[n][i];
		if (i == 0 || n == i)
			dp[n][i] = 1;
		else
			dp[n][i] = f(n - 1, i) + f(n - 1, i - 1);
		return dp[n][i];
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int n = in.nextInt(), k = in.nextInt();
			long ans = 0;
			for (int i = 0; i <= n / 2; i++) {
				ans += f(n - i, i) * Math.pow(k - 1, n - i);
			}
			System.out.println(ans);
		}
		in.close();
	}
}