E - Roaming

题目描述

一共有n个房间，每一个房间里都有一个人，现在有k次移动，某个人从一个房间走到另一个房间为一次移动。问k次移动，n个房间的情况数有多少种？


分析

这题可以使用枚举空位的做法来做。如果要移动k次，因为最多只能有n-1个空位,所以空位的数量<=min(n-1,k),例如移动5次，留下2个空位，另外3次移动是两个房间的人相互对换。之后就开始枚举空位数量的情况，然后进行累加。

假如现在空位数 = i，那么我们现在需要先选出i个房间进行令其为空，也就是C(n,i),然后需要把n个人分成n-i部分，我们可以把n个人想像成一排小球，现在要分成n-i段，所以需要n-i-1个隔板插入n-1个空位，就分成了n-i段

举个例子

现在假如n = 5，选出2个空位

房间1 房间2=0 房间3 房间4=0 房间5
现在我们需要将n个人分成3部分放在房间1，3，5中
那么对于这个序列 1 1 1 1 1，一共有4个空隙，只要我们插入2个板子就分成了3段，形成了3部分,然后把这三段依次放入到房间1,3,5中

AC 代码

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e6+10;
const ll mod = 1000000007;
ll n,k;
ll f1[maxn],f2[maxn],inv[maxn];

void init(){ // 初始化maxn范围内的阶乘，和阶乘的逆元
    inv[1] = 1;
    for(int i = 2;i<maxn;i++) inv[i] = (mod-mod/i)*inv[mod%i]%mod;
    f1[0] = f2[0] = 1;
    for(int i = 1;i<maxn;i++){
        f1[i] = f1[i-1]*i%mod;
        f2[i] = f2[i-1]*inv[i]%mod;
    }
}

ll C(ll n,ll k){ //使用公式计算C(n,k)
    return f1[n]*f2[k]%mod*f2[n-k]%mod;
}

int main(){
    init();
    cin>>n>>k;
    ll res = 0;
    for(ll i = 0;i<=min(n-1,k);i++){
        res = (res + C(n,i)*C(n-1,n-i-1)%mod)%mod;
    }
    cout<<res<<endl;
    return 0;
}