Nhận xét:

Với mọi số nguyên tố ~p~, gọi ~p_x~, ~p_y~, ~p_z~ lần lượt là số mũ của cơ số ~p~ trong phân tích thừa số nguyên tố của ~X~, ~Y~ và ~Z~, ta có ~p_y \leq p_z \leq p_x~. Bên cạnh đó, tổng các ~p_z~ (với mọi số nguyên tố ~p~) không vượt quá ~k~.

Lưu ý: các giá trị ~p~ không xuất hiện trong phân tích thừa số nguyên tố của ~X~ thì xem như ~p_x = 0~, tương tự với ~p_y~ và ~p_z~.

Với mỗi số nguyên tố ~p~, xem ~p_y, p_x~ như một cặp số ~(l, r)~, bài toán chuyển về như sau:

Có ~n~ cặp số ~(l, r)~, với mỗi cặp ~(l_i, r_i)~ cần chọn một số nguyên trong đoạn ~[l_i;r_i]~ sao cho tống các số được chọn không vượt quá ~k~.

Lưu ý, ta chỉ quan tâm đến những cặp ~(p_y, p_x)~ mà ~p~ xuất hiện trong phân tích thừa số của ~X~ hoặc ~Y~, vì khi ~p~ không xuất hiện trong cả hai thì ~p_x = p_y = 0~, vậy ~p_z = 0~ và không ảnh hưởng đến tổng các số được chọn.

Trong trường hợp số tồn tại ~p_y > p_x~, đáp án chắc chắn bằng ~0~.

Trở lại với bài toán, ta sử dụng quy hoạch động để giải quyết, cụ thể như sau. Gọi ~dp[i][j]~ là số cách chọn ~i~ số cho ~i~ cặp ~(l, r)~ đầu tiên mà tổng ~i~ số đó bằng ~j~.

Ta có ~dp[i][j] = \sum_{k = max(0, j - r_i)}^{j - l_i} dp[i - 1][j]~ ~\forall j \geq l_i~.

Để tính nhanh được tổng trên có thể dùng tổng tiền tố.

Độ phức tạp của thuật toán là ~O(n \times q)~.

Code mẫu

//TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int , int>
#define fi first
#define se second
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x)  (1LL<<(x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"  

using namespace std;
const int N = 110;
const int K = (int)1e5+228;
const int mod = (int)1e9+7;

void add(int &x, const int &y)
{
    x += y;
    if(x >= mod) x -= mod;
}
void sub(int &x, const int &y)
{
    x -= y;
    if(x < 0) x += mod;
}
#define PRODUCT(x,y) (1LL*(x)*(y)%mod)

int power(int x, int y)
{
    int res = 1;
    while(y > 0)
    {
        if(1&y) res = PRODUCT(res, x);
        x = PRODUCT(x, x);
        y /= 2;
    }
    return res;
}

int n, m, k, a[N], p[N], b[N], q[N];
int need[N];
map<int, int> pos;
int dp[N][K];

void solve()
{
    cin >> k;
    cin >> n;
    for(int i=1; i<=n; ++i) cin >> a[i];
    for(int i=1; i<=n; ++i) cin >> p[i], pos[p[i]] = i;
    cin >> m;
    for(int i=1; i<=m; ++i) cin >> b[i];
    for(int i=1; i<=m; ++i)
    {
        cin >> q[i];
        if(pos[q[i]] == 0)
        {
            cout << 0;
            return;
        }
        need[pos[q[i]]] = b[i];
    }

    for(int i=1; i<=n; ++i)
    {
        if(a[i] < need[i])
        {
            cout << 0;
            return;
        }
    }

    for(int i=0; i<=k; ++i)
        dp[0][i] = 1;
    for(int i=1; i<=n; ++i)
    {
        for(int j=0; j<=k; ++j)
        {
            if(j > 0)
                add(dp[i][j], dp[i][j-1]);
            int l = need[i], r = min(j, a[i]);
            if(l > r) continue;
            add(dp[i][j], dp[i-1][j-l]);
            if(j - r > 0)
                sub(dp[i][j], dp[i-1][j-r-1]);
        }
    }
    cout << dp[n][k];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    //cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}