Intro

• 來源：E.Ethernet - Codeforces
• 題意：給定 \(n(1\le n\le 10)\) 個數組成的排列，其中前 \(m(0\le m\le n)\) 個數(即\(1\)~\(m\)) 在排列中位置隨機，對于剩余 \(n-m\) 個數，設當前填充數字為\(i(n-m\le i\le n)\)：
  • 若第 \(i\) 位未被填充，則填充數字\(i\)；
  • 否則， \(i\) 將被隨機填充到先前未被填充的位上。
• 關鍵詞：搜索，思維(簽到)

題解

下面給出兩種解法：

DFS

注意到 \(n=10\)，顯而易見這是一道DFS板子題，不需要任何剪枝技巧，復雜度\(O(n!)\)。

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,yes;
vector<bool>v(11);
void dfs(int x){//x:當前處理數字
    if(x==n){//插滿
        cnt++;
        if(!v[n]) yes++;
    }else if(x>m){//亂插結束
        if(!v[x]){
            v[x]=1;
            dfs(x+1);
            v[x]=0;
        }else{//亂插
            for(int i=1;i<=n;i++)
                if(!v[i]){
                    v[i]=1;
                    dfs(x+1);
                    v[i]=0;
                }
        }
    }else{
        for(int i=1;i<=n;i++)
	        if(!v[i]){
	              v[i]=1;
	              dfs(x+1);
	              v[i]=0;
          	}
    }
}
void solve(){
    cin>>n>>m;
    dfs(1);
    printf("%.10lf",yes/(double)cnt);
}
signed main(){
    // ios::sync_with_stdio(0),cin.tie(0);
    int t=1;
    while(t--) solve();
    return 0;
}

結論

手玩幾個樣例，不難發現：
若\(n=m\)，則答案為\(\frac{1}{m}\)；否則答案為\(\frac{1} {m+1}\)。

#include<bits/stdc++.h>
using namespace std;
int n,k;
void solve(){
	if(n==k) printf("%.10lf",1/(double)k);
    else printf("%.10lf",1/(double)(k+1));
}
signed main(){
    scanf("%lld %lld",&n,&k);
	solve();
    return 0;
}