解题思路:
对于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(); } }
0.0分
0 人评分
矩形面积交 (C语言代码)浏览:1514 |
C语言训练-计算t=1+1/2+1/3+...+1/n (C语言代码)浏览:868 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:539 |
WU-字符串比较 (C++代码)浏览:756 |
最小公倍数 (C语言代码)浏览:1029 |
幸运数 (C++代码)浏览:1264 |
2004年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:599 |
星期判断机 (C语言代码)浏览:859 |
C语言程序设计教程(第三版)课后习题12.1 (C语言代码)浏览:646 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:474 |