# Lời giải
- Vì **không được xếp các cây nấm đứng liền kề nhau**, nên ta có thể hiểu như sau:
Sau khi chọn m cây nấm, ta cần đặt m-1 khoảng trống để ngăn cách chúng.
- Như vậy, số vị trí thực sự còn lại để đặt nấm là:
n - (m - 1) = n - m + 1
- Do đó, bài toán trở thành: **chọn m vị trí trong tổng số (n - m + 1) vị trí**
→ Đáp án = C(n - m + 1, m)
---
# Code
```cpp
#include<bits/stdc++.h>
#define ll long long
#define nl '\n'
#define f0(i,a,b) for (int i = a, _b = b; i < _b; i++)
#define f1(i,a,b) for (int i = a, _b = b; i <= _b; i++)
#define rf(i,a,b) for (int i = a, _b = b; i >=_b; i--)
#define fi first
#define se second
#define Size(a) (int)a.size()
#define bit(mask, i) ((mask>>i)&1)
#define Mask(i) (1<<(i))
using namespace std;
const int Maxn = 1e5+5;
const int mod = 1e9+7;
int n, m;
int fact[Maxn], inv[Maxn];
ll Pow(ll a, ll b) {
ll res = 1;
while(b) {
if (b&1) res = res * a % mod;
a = (1ll*a*a)%mod;
b/=2;
}
return res;
}
void solve(int n) {
fact[0] = 1;
f1(i,1,n) fact[i] = 1ll*fact[i-1]*i % mod;
inv[n] = Pow(fact[n], mod-2);
rf(i,n-1,0) inv[i] = 1ll*inv[i+1]*(i+1)%mod;
}
ll C(int n, int k) {
if (k < 0 || k > n) return 0;
return 1ll*fact[n]*inv[k]%mod*inv[n-k]%mod;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
int need = n - (m - 1);
solve(1e5);
cout << C(need, m);
return 0;
}
```
zxcvbnm0123toi
Created at
1 likes