# Hướng dẫn
Gọi **f[i][j]** là số cách lấy được **k** quyển sách từ **i** cái kệ sách đầu tiên. Đây là một bài **DP 0-1**, nghĩa là
lấy hoặc không lấy.\
**THCS:** f[0][0] = 1. Có 1 cách để lấy được 0 quyển sách từ 0 kệ sách.\
**TH1**: Không lấy sách từ kệ thứ i. Nghĩa là đã có đủ j quyển sách.
- f[i][j] = f[i-1][j]
**TH2:** Lấy sách từ kệ thứ i. Nghĩa là còn thiếu 1 quyển để có đủ j quyển sách.
- f[i][j] = f[i][j] + f[i-1][j-1] * a[i] (Áp dụng Quy tắc nhân)
Code:
```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,a,b) for (int i=a; i<=b; ++i)
const int MAXN = 1e3 + 5;
const ll MOD = 1e9 + 7;
int n,k;
int a[MAXN];
int f[MAXN][MAXN];
inline ll add(const ll &a, const ll &b)
{
return (a % MOD + b % MOD) % MOD;
}
inline ll mul(const ll &a, const ll &b)
{
return (a % MOD * b % MOD) % MOD;
}
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> k;
FOR(i,1,n) cin >> a[i];
f[0][0] = 1;
FOR(i,1,n)
{
FOR(j,0,k)
{
f[i][j] = f[i-1][j];
if (j > 0) f[i][j] = add(f[i][j], mul(f[i-1][j-1], a[i]));
}
}
return cout << f[n][k], 0;
}
```
hungkm466
Created at
1 likes