Ở bài này, ta gọi **f[i][j]** là số lượng mảng có độ dài i và kết thúc tại giá trị j.
Trường hợp cơ sở ở đây là: **f[1][j] = 1 (0 <= j <= k)**
=> Vì mảng chỉ có một phần tử luôn thoả mãn
Công thức truy hồi của bài này là:
**f[i][j] += f[i-1][x] (với x + j là một số nguyên tố, 0 <= x <= k)**
Kết quả của bài toán sẽ là tổng của: **f[n][j] (0 <= j <= k)**
**Code tham khảo:**
// Author: Tran Minh Tuan
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define el "\n"
#define name ""
using namespace std;
const int N = 1005;
const ll oo = (ll)9e18 + 7;
const int MOD = (int)1e9 + 7;
int n, k;
ll f[105][N];
int snt[2*N];
vector<int> prime;
void sang() {
snt[0] = snt[1] = 1;
for (int i = 2; i * i <= 2*N; ++i){
if (!snt[i])
for (int j = i*i; j <= 2*N; j+=i) snt[j] = 1;
}
for (int i = 2; i <= 2*k; i++)
if (!snt[i]) prime.pb(i);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
cin >> n >> k;
sang();
for (int j = 0; j <= k; ++j) f[1][j] = 1;
for (int i = 2; i <= n; ++i){
for (int j = 0; j <= k; ++j) {
for (int x : prime){
if (x >= j && x - j <= k) f[i][j] = (f[i][j] % MOD + f[i-1][x - j] % MOD) % MOD;
}
}
}
ll res = 0;
for (int j = 0; j <= k; ++j) res = (res % MOD + f[n][j] % MOD) % MOD;
cout << res;
return 0;
}
tmtuan_2k8
Created at
2 likes