Dễ thấy, các số ở hai mảng ~a~ và ~b~ luôn đi chung theo cặp, vì vậy ta sẽ chia ~n~ số thành ~2~ nhóm: nhóm ~X~ gồm các số ~a_i~ có ~b_i=1~ và nhóm ~Y~ gồm các số ~a_i~ có ~b_i=0~. Giả sử ~|X|=x~ và ~|Y|=y~ (~x + y = n~).

Với mọi hoán vị ~p=[p_1,p_2,…,p_n]~, trong nhóm ~X~ luôn tồn tại ~\lceil \frac{x}{2} \rceil~ số mang dấu ~+~ và ~\lfloor \frac{x}{2} \rfloor~ số mang dấu ~-~. Trong khi đó, ở nhóm ~Y~, số lượng số mang dấu ~+~ và dấu ~–~ lại không cố định mà phụ thuộc vào hoán vị ~p~.

Xét tập ~Y~: dễ thấy, ~a_{p_i}~ sẽ mang dấu ~+~ nếu số bit ~1~ trong đoạn ~b_{p_1},b_{p_2},\ldots,b_{p_{i - 1}}~ là chẵn; và mang dấu ~–~ nếu số bit 1 trong đoạn ~b_{p_1},b_{p_2},\ldots,b_{p_{i - 1}}~ là lẻ.

Ta sẽ có được cách làm như sau: Xét mảng ~b_{p_1},b_{p_2},\ldots,b_{p_{n}}~, dễ thấy mảng này luôn có dạng

~\ldots\ |1|\ldots |1| \ldots |1| \ldots~

với ~\ldots~ là chuỗi các bit ~0~.

Gọi các khoảng ~\ldots~ này là ~1~ túi. Ta định nghĩa ~1~ túi là túi dương nếu chúng nằm sau một lượng lẻ bit ~1~, và túi âm nếu chúng nằm sau một lượng chẵn bit ~1~. Dễ thấy ta có ~\lceil \frac{x}{2} \rceil~ túi dương và ~\lceil \frac{x + 1}{2} \rceil~ túi âm. Nếu ~b_{p_i}~ nằm trong túi dương, ~a_{p_i}~ sẽ mang dấu ~+~ và ngược lại, nếu ~b_{p_i}~ nằm trong túi âm, ~a_{p_i}~ sẽ mang dấu ~-~.

Đây chính là bài toán chia kẹo Euler (stars-and-bars): nếu trong tập ~Y~ có ~z~ số mang dấu ~+~, ta sẽ bỏ ~z~ số này vào ~\lceil \frac{x}{2} \rceil~ túi dương, và bỏ ~y- z~ số còn lại vào ~\lceil \frac{x + 1}{2} \rceil~ túi âm. Ngoài ra, vì thứ tự của các số này là quan trọng, số cách sắp xếp cuối cùng sẽ là:

~\displaystyle \binom{z + \lceil \frac{x}{2} \rceil - 1}{\lceil \frac{x}{2} \rceil - 1} \cdot z! \cdot \binom{y -z + \lceil \frac{x+1}{2} \rceil - 1}{\lceil \frac{x+1}{2} \rceil - 1} \cdot (y - z)!~

Giả sử ta chia tập ~X~ thành ~2~ phần (mỗi phần lần lượt có ~\lceil \frac{x}{2} \rceil~ và ~\lfloor \frac{x}{2} \rfloor~ phần tử), và hiệu của ~2~ phần này đồng dư với ~r (\text{mod k})~ (có ~f[r]~ cách). Khi ấy, chúng ta sẽ đếm số cách chia tập ~Y~ thành ~2~ phần (mỗi phần lần lượt có ~z~ và ~y - z~ phần tử, ~0 \le z \le y~), và hiệu của ~2~ phần này đồng dư với ~k-r (\text{mod k})~ (có ~g[z][k - r]~ cách). Việc đếm số cách chia này có thể dễ dàng xử lý bằng quy hoạch động knapsack.

Số cách sắp xếp cho mỗi trường hợp như trên sẽ là:

~\displaystyle f[r] \cdot \lceil \frac{x}{2} \rceil ! \cdot \lfloor \frac{x}{2} \rfloor ! \cdot g[z][k - r] \cdot \binom{z + \lceil \frac{x}{2} \rceil - 1}{\lceil \frac{x}{2} \rceil - 1} \cdot z! \cdot \binom{y - z + \lceil \frac{x+1}{2} \rceil - 1}{\lceil \frac{x+1}{2} \rceil - 1} \cdot (y - z)!~

Đáp án của bài toán là tổng của tất cả các trường hợp.

Độ phức tạp: ~O(kn^2)~.

Code mẫu

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
inline void add(int &x, int y) { 
    x += y;
    while (x >= MOD) x -= MOD;
}
inline int mul(int x, int y) {
    return (x * 1LL * y) % MOD;
}
inline int pw(int x, int y) {
    int z = 1;
    while (y) {
        if (y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}

const int N = 500 + 3, K = 500 + 3;
int n, k, a[N], b[N];
int x, y, X[N], Y[N];
int fX[2][N][K], fY[2][N][K];
int fact[N], inv_fact[N];

int C(int n, int k) {
    if (n < k || k < 0) return 0;
    return mul(fact[n], mul(inv_fact[k], inv_fact[n - k]));
}

void calc_dp(int m, int t[N], int f[2][N][K]) {
    f[0][0][0] = 1;
    for (int i = 1; i <= m; ++i) {
        for (int j = 0; j <= i; ++j) {
            for (int r = 0; r < k; ++r) {
                f[i & 1][j][r] = f[(i & 1) ^ 1][j][(r + t[i]) % k];
                if (j > 0) add(f[i & 1][j][r], f[(i & 1) ^ 1][j - 1][(r - t[i] + k) % k]);
            }
        }
    }
}

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        cin >> a[i], a[i] %= k;
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
        if (b[i] > 0) X[++x] = a[i];
        else Y[++y] = a[i];
    }

    calc_dp(x, X, fX);
    calc_dp(y, Y, fY);

    fact[0] = 1;
    for (int i = 1; i <= n; ++i)
        fact[i] = mul(fact[i - 1], i);
    inv_fact[n] = pw(fact[n], MOD - 2);
    for (int i = n - 1; i >= 0; --i)
        inv_fact[i] = mul(inv_fact[i + 1], i + 1);

    if (!x) {
        int sum = 0;
        for (int i = 1; i <= n; ++i)
            (sum += a[i]) %= k;
        if (sum != 0) cout << 0;
        else cout << fact[n] << '\n';
        return;
    }

    int ans = 0;
    int plus_sack = (x + 1) / 2, negative_sack = x / 2 + 1;
    for (int rem_x = 0; rem_x < k; ++rem_x) {
        int rem_y = k - rem_x;
        if (rem_y == k) rem_y -= k;

        int tX = mul(fX[x & 1][(x + 1) / 2][rem_x], mul(fact[(x + 1) / 2], fact[x / 2]));
        for (int plus_sign = 0; plus_sign <= y; ++plus_sign) {
            int tY = fY[y & 1][plus_sign][rem_y];

            tY = mul(tY, C(plus_sign + plus_sack - 1, plus_sack - 1));
            tY = mul(tY, fact[plus_sign]);

            int negative_sign = y - plus_sign;
            tY = mul(tY, C(negative_sign + negative_sack - 1, negative_sack - 1));
            tY = mul(tY, fact[negative_sign]);

            add(ans, mul(tX, tY));
        }
    }

    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}