# 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;
}
```
Gọi dp[i][j] là số cách lấy j quyển sách từ i kệ đầu tiên
THCS: dp[0][0] = 1
dp[0][1….k] = 0
CT:
Nếu không lấy quyển sách thứ i:
dp[i][j] = dp[i][j] + dp[i -1][j]
Tức là số cách lấy j quyển sách từ i kệ sách đầu tiên sẽ + thêm với số cách lấy j quyển sách từ i - 1 kệ sách đầu tiên
Nếu lấy quyển sách từ kệ thứ i (kệ thứ i có >=1 quyển sách)
dp[i][j] = dp[i][j] + dp[i-1][j-1] là số cách lấy từ kệ thứ i quyển sách thứ i_1
….
dp[i][j] = dp[i][j] + dp[i-1][j-1] là số cách lấy từ kệ thứ i quyển sách thứ A_i
Nếu kệ thứ i có A_i cuốn sách , ta có ct:
dp[i][j] = dp[i][j] + (dp[i-1][j-1] + ….. dp[i-1][j-1])
A_i lần
Kết quả: dp[n][k];
# NHỚ %MOD nhe
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
int main(){
ll n, k;
cin >> n >> k;
ll a[n + 1]; for(int i = 1; i <= n; i++) cin >> a[i];
vector< vector<ll> > dp(n + 1, vector<ll>(k + 1, 0));
dp[0][0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 0; j <= k; j++){
dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD;
if(j >= 1)
dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] % MOD * a[i] % MOD) % MOD;
}
}
cout << dp[n][k];
return 0;
}
hungkm466
Created at
16 likes
nguyenthenhanlqd329
Created at
0 likes