题目翻译： #
点击查看。
思路： #
使用动态规划，计算在给定的字母表上，长度为 $n$ 的所有可能单词中，“紧致”单词的数量。
然后，通过这个数量除以所有可能的单词数量来计算出“紧致”单词的百分百。
对于 $dp_{i,j}$，其中 $i$ 表示长度为 $i$，$j$ 表示以 $j$ 结尾，当长度为 $1$ 时，每个数字 $j$ 都是一个“紧致”单词，因此我们可以初始化所有 $dp_{1,j}$ 为 $1$，其中 $0 \le j \le k$。
对于 $i$ 不等于 $1$ 时的 $dp_{i,j}$ 等于什么呢？这需要分类讨论。
对于长度为 $i$ 且以数字 $j$ 结尾的单词，它可以从以下几种情况转移而来：
- 长度为 $i-1$ 且以数字 $j$ 结尾的单词。
- 长度为 $i-1$ 且以数字 $j-1$ 结尾的单词，注意 $j$ 需要大于 $0$。
- 长度为 $i-1$ 且以数字 $j+1$ 结尾的单词，注意 $j$ 需要小于 $k$。
因此，动态转移方程在 c++ 中可以表示为：
dp[i][j]+=dp[i-1][j];
if(j!=0)dp[i][j]+=dp[i-1][j-1];
if(j!=k)dp[i][j]+=dp[i-1][j+1];
代码： #
#include<bits/stdc++.h>
using namespace std;
int n,k;
double dp[110][15];
void solve(){
memset(dp,0,sizeof(dp));
for(int i=0;i<=k;i++)dp[1][i]=1;
for(int i=2;i<=n;i++){
for(int j=0;j<=k;j++){
dp[i][j]+=dp[i-1][j];
if(j!=0)dp[i][j]+=dp[i-1][j-1];
if(j!=k)dp[i][j]+=dp[i-1][j+1];
}
}
double sum=0;
double kn=pow(k+1,n);
for(int i=0;i<=k;i++)sum+=dp[n][i];
// cout<<sum<<" "<<kn<<"\n";
double ans=sum*100;
ans/=kn;
printf("%.5lf\n",ans);
// cout<<fixed<<setprecision(5)<<(sum*100.0)/kn<<"\n";
return;
}
int main(){
while(cin>>k>>n)solve();
return 0;
}