大意略。
思路:长度从一开始统计共有多少种情况,然后除以排列总数即可,必须用double存,long long 与 unsigned long long 都会爆。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <cassert> using namespace std; typedef unsigned long long ULL; int n, k; double d[20][120]; double pow1(int n, int base) { double s = 1.; for(int i = 1; i <= n; i++) s *= base; return s; } double dp() { memset(d, 0, sizeof(d)); for(int i = 0; i <= k; i++) d[i][1] = 1.; for(int j = 2; j <= n; j++) { for(int i = 0; i <= k; i++) { if(i == 0) {d[i][j] = d[i][j-1] + d[i+1][j-1];} else if(i == k) {d[i][j] = d[i-1][j-1] + d[i][j-1];} else {d[i][j] = d[i-1][j-1] + d[i][j-1] + d[i+1][j-1];} } } double s = 0; for(int i = 0; i <= k; i++) s += d[i][n]; return s; } void solve() { double ans = dp(); double m = pow1(n, k+1); double f = ans / m * 100.; printf("%.5lf\n", f); } int main() { while(~scanf("%d%d", &k, &n)) { solve(); } return 0; }