头像

CLB




离线:11个月前


最近来访(0)


CLB
11个月前

模仿主席树的思路打了一个代码。
每一个点插入以后合并,查询的时候要注意一下边界问题就好。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 6e5 + 10, M = N * 32;

int cnt, trie[M][2], rt[N];

int n, m;

void insert(int p, int x) {
    for (int i = 30; i >= 0; i--)
        trie[p][x >> i & 1] = ++cnt, p = cnt;
}

void merge(int &x, int y) {
    if (!x) { x = y; return;}
    if (!y) return;
    merge(trie[x][0], trie[y][0]);
    merge(trie[x][1], trie[y][1]);
}

int calc(int l, int r, int x) {
    int ans = 0;
    for (int i = 30; i >= 0; i--) {
        int p = x >> i & 1;
        if (trie[l][p ^ 1] != trie[r][p ^ 1]) ans += (1 << i), l = trie[l][p ^ 1], r = trie[r][p ^ 1];
        else if (trie[r][p]) l = trie[l][p], r = trie[r][p];
        else break;
    }
    return ans;
}

int main() {
    rt[0] = ++cnt, insert(rt[0], 0);
    cin >> n >> m; int now = 0;
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x); now ^= x;
        rt[i] = ++cnt, insert(rt[i], now);
        merge(rt[i], rt[i - 1]);
    }
    while (m--) {
        char s[5]; scanf("%s", s);
        if (s[0] == 'A') {
            int x; scanf("%d", &x); now ^= x;
            rt[++n] = ++cnt; insert(rt[n], now);
            merge(rt[n], rt[n - 1]);
        }
        else {
            int l, r, x; scanf("%d%d%d", &l, &r, &x);
            x ^= now;
            if (r == 1) { printf("%d\n", x); continue;}
            int ans = calc(l > 1 ? rt[l - 2] : rt[l - 1], rt[r - 1], x);
            printf("%d\n", l > 1 ? ans : max(ans, x));
        }
    }
    return 0;
}



CLB
11个月前

这道题真的恶心,我花了一上午的时间才A。

对比了一下其他人的代码,我感觉自己的代码十分冗长。

分块肯定是要的,分块完以后处理一下块中各种花的前缀和,并对于同种花在同一个块内搞一个倍增,这样可以快速的找出同种花的个数。顺便记录每一个块开头到任意一个点的众数。

查询的时候只需要找左边不在整块内的花,然后用倍增和前缀和查找出所有同种类的花,然后比较最大值。

上面有很多细节已经省略,请看代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 4e4 + 10, M = 5e4 + 10, K = 210;
int n, m, q, a[N], b[N];
int get(int x) {
    int l = 1, r = m, mid, ans;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (b[mid] <= x) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    return ans;
}

int cnt, L[K], R[K], p[N];
//s[K][N] 前缀和
//nxt[N][10] 倍增 
//head[K][N] 块中第一个 
//zs[K][N] 块头到某个点的众数,num[K][N]个数

int s[K][N], nxt[N][10], head[K][N], zs[K][N], num[K][N]; 

int last[N], sum[N];

bool vis[N]; int tp, sta[N];

int getl(int now) {
    int sum = 1;
    for (int j = 8; j >= 0; j--) 
        if (nxt[now][j]) now = nxt[now][j], sum += (1 << j);
    return sum;
}

int getr(int now, int y) {
    if (!now || now > y) return 0;
    int sum = 1, p = 1;
    while (p > 0) {
        if (!nxt[now][p - 1]) p--;
        else {
            if (nxt[now][p - 1] <= y) now = nxt[now][p - 1], sum += 1 << (p - 1), p++;
            else p--;
        }
    }
    return sum;
}

int main() {
    freopen("2.in", "r", stdin);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1); m = 1;
    for (int i = 2; i <= n; i++)
        if (b[i] != b[i - 1]) b[++m] = b[i];
    for (int i = 1; i <= n; i++) a[i] = get(a[i]);
    int block = 3, cnt = (n - 1) / block + 1;
    for (int i = 1; i <= cnt; i++) {
        L[i] = R[i - 1] + 1;
        R[i] = R[i - 1] + block;
        if (i == cnt) R[i] = n;
        for (int j = L[i]; j <= R[i]; j++) p[j] = i;
    }
    for (int i = 1; i <= cnt; i++) {
        for (int j = 1; j <= m; j++) s[i][j] = s[i - 1][j], last[j] = sum[j] = 0;
        for (int j = L[i]; j <= R[i]; j++) {
            s[i][a[j]]++;
            if (head[i][a[j]] == 0) head[i][a[j]] = j;
            if (last[a[j]]) nxt[last[a[j]]][0] = j;
            last[a[j]] = j;
        }
        int maxx = 0;
        for (int j = L[i]; j <= n; j++) {
            sum[a[j]]++;
            if ((sum[a[j]] > sum[maxx]) || (sum[a[j]] == sum[maxx] && a[j] < maxx)) maxx = a[j];
            zs[i][j] = maxx; num[i][j] = sum[maxx];
        }
    }
    for (int j = 1; j <= 8; j++)
        for (int i = 1; i <= n; i++)
            nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
    int lastans = 0;
    for (int i = 1; i <= q; i++) {
        int x, y; scanf("%d%d", &x, &y);
        x = (x + lastans - 1) % n + 1;
        y = (y + lastans - 1) % n + 1;
        if (x > y) swap(x, y);
        int l = L[p[x]] == x ? p[x] : p[x] + 1;
        int r = R[p[y]] == y ? p[y] : p[y] - 1;
        if (l > r) {
            int maxx = 0, hh;
            if (p[x] == p[y]) {
                for (int i = x; i <= y; i++)
                    if (!vis[a[i]]) {
                        vis[a[i]] = 1; sta[++tp] = a[i];
                        int now = i, sum = getr(now, y);
                        if (sum > maxx || (sum == maxx && hh > a[i])) maxx = sum, hh = a[i];
                    }
            }
            else {
                for (int i = x; i <= y; i++) {
                    if (vis[a[i]]) continue;
                    vis[a[i]] = 1; sta[++tp] = a[i];
                    int sum = 0, now = i;
                    if (i <= R[p[x]]) sum += getl(now);
                    now = head[p[y]][a[i]];
                    sum += getr(now, y);
                    if (sum > maxx || (sum == maxx && hh > a[i])) maxx = sum, hh = a[i];
                }
            }
            printf("%d\n", lastans = b[hh]);
        }
        else {
            int p1 = zs[l][y], s1 = num[l][y];
            if (L[p[x]] == x) { printf("%d\n", lastans = b[p1]); continue;}
            int maxx = 0, hh;
            for (int i = x; i < L[l]; i++) {
                if (vis[a[i]]) continue;
                if (a[i] == p1) {s1++; continue;}
                vis[a[i]] = 1; sta[++tp] = a[i];
                int sum = s[r][a[i]] - s[l - 1][a[i]], now;
                now = i; sum += getl(now);
                if (y != R[p[y]]) now = head[p[y]][a[i]], sum += getr(now, y);
                if (sum > maxx || (sum == maxx && hh > a[i])) maxx = sum, hh = a[i];
            }
            if (s1 > maxx || (s1 == maxx && p1 < hh)) printf("%d\n", lastans = b[p1]);
            else printf("%d\n", lastans = b[hh]);
        }
        while (tp) vis[sta[tp--]] = 0;
    }
    return 0;
}



CLB
11个月前

不多说了,代码含注释

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
//a[i]表示1 ~ i-1有多少个比b[i]小的
//1 ~ i-1 > b[i] = i - 1 - a[i]
//i+1 ~ n  < b[i] = b[i] - 1 - a[i]
//i+1 ~ n  > b[i] = n - b[i] - (i - 1 - a[i]) = n - i + 1 + a[i] - b[i]
int n, /* a[N], b[N],*/ c[N];

void add(int x) {
    for (; x <= n; x += x & -x) c[x]++;
}
int get(int x) {
    int s = 0;
    for (; x; x -= x & -x) s += c[x];
    return s;
}

int main() {
    cin >> n;
/*  for (int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
        a[i] = get(b[i] - 1);
        add(b[i]);
    }
    LL s1 = 0, s2 = 0;
    for (int i = 2; i < n; i++) {
        s1 += 1ll * (i - 1 - a[i]) * (n - i + 1 + a[i] - b[i]);
        s2 += 1ll * a[i] * (b[i] - 1 - a[i]);
    }*/
    LL s1 = 0, s2 = 0;
    for (int i = 1; i <= n; i++) {
        int b; scanf("%d", &b);
        int a = get(b - 1);
        add(b);
        s1 += 1ll * (i - 1 - a) * (n - i + 1 + a - b);
        s2 += 1ll * a * (b - 1 - a);
    }

    cout << s1 << " " << s2 << endl;
    return 0;
}



CLB
11个月前

拓展域怎么搞,书上面肯定讲了。
在这一道题里面,有一个比较难搞的地方,那就是假话的关系是不能保存在并查集里面。
但是我们又需要用并查集判断某个生物拆成的三个点是否在同一集合内,而直接复制fa肯定会超时。
所以我们用一个栈来存储修改过的fa,然后跑并查集,如果是假话,那就把fa修改回原来的样子。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 5e4 + 10;
int n, k, fa[N], tp, a[N], b[N];

int findfa(int x) {
    if (x == fa[x]) return x;
    a[++tp] = x; b[tp] = fa[x];
    return fa[x] = findfa(fa[x]);
}

void merge(int x, int y) {
    int fx = findfa(x);
    int fy = findfa(y);
    if (fx != fy) {
        a[++tp] = fx; b[tp] = fa[fx];
        fa[fx] = fy;
    }
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= 3 * n; i++) fa[i] = i;
    int ans = 0;
    for (int i = 1; i <= k; i++) {
        int d, x, y;
        scanf("%d%d%d", &d, &x, &y);
        if (x > n || y > n) { ans++; continue; }
        if (d == 2 && x == y) { ans++; continue; }
        tp = 0;
        if (d == 1) merge(x, y), merge(x + n, y + n), merge(x + n + n, y + n + n);
        else merge(x, y + n), merge(x + n, y + n + n), merge(x + n + n, y);
        if (findfa(x) == findfa(x + n) || findfa(x) == findfa(x + n + n) || findfa(x + n) == findfa(x + n + n) ||
            findfa(y) == findfa(y + n) || findfa(y) == findfa(y + n + n) || findfa(y + n) == findfa(y + n + n)) {
            ans++;
            while (tp--) fa[a[tp]] = b[tp];
        }
    }
    cout << ans << endl; return 0;
}



CLB
11个月前

一道很有意思的概率dp题。
一开始我是想求出到达$c_i/d_i$教室的期望值,后面发现这样做有bug。
又读了一遍题目,发现我们要求如何提交申请使得期望值最小,所以在dp的时候必须要以是提交申请为状态
于是我分类讨论了一下状态转移(假设n只有2):
注:上面的点表示成功,下面的点表示失败,b表示概率

情况一,1换,2不换
无标题.png

情况二,1换,2换
1.png

情况三,1不换,2换
3.png

情况四,1不换,2不换
4.png

然后就可以dp了

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 2e3 + 10, M = 3e2 + 10;
int n, m, V, E, c[N], d[N], a[M][M];
double b[N], f[2][N][2]; 
void init(int p) {for (int i = 0; i <= m; i++) f[p][i][0] = f[p][i][1] = 1000000000.0;}
int main() {
    cin >> n >> m >> V >> E;
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= n; i++) cin >> d[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    memset(a, 0x3f, sizeof(a));
    for (int i = 1; i <= V; i++) a[i][i] = 0;
    for (int i = 1; i <= E; i++) {
        int x, y, z; scanf("%d%d%d", &x, &y, &z);
        if (z < a[x][y]) a[x][y] = a[y][x] = z;
    }
    for (int k = 1; k <= V; k++)
        for (int i = 1; i <= V; i++)
            for (int j = 1; j <= V; j++)
                if (a[i][j] > a[i][k] + a[k][j])
                    a[i][j] = a[i][k] + a[k][j];
    init(0); f[0][0][0] = f[0][1][1] = 0.0;
    int p = 0;
    for (int i = 2; i <= n; i++) {
        p ^= 1; init(p);
        for (int j = 0; j <= m; j++) {
            f[p][j][0] = f[p ^ 1][j][0] + 1.0 * a[c[i - 1]][c[i]];
            if (j) f[p][j][0] = min(f[p][j][0], f[p ^ 1][j][1] + 1.0 * b[i - 1] * a[d[i - 1]][c[i]] + 1.0 * (1.0 - b[i - 1]) * a[c[i - 1]][c[i]]);
            if (!j) continue;
            f[p][j][1] = f[p ^ 1][j - 1][0] + 1.0 * b[i] * a[c[i - 1]][d[i]] + 1.0 * (1.0 - b[i]) * a[c[i - 1]][c[i]];
            if (j > 1) f[p][j][1] = min(f[p][j][1], f[p ^ 1][j - 1][1] + 1.0 * b[i - 1] * (1.0 - b[i]) * a[d[i - 1]][c[i]] + 1.0 * (1.0 - b[i - 1]) * (1.0 - b[i]) * a[c[i - 1]][c[i]] + 1.0 * b[i - 1] * b[i] * a[d[i - 1]][d[i]] +1.0 * (1.0 - b[i - 1]) * b[i] * a[c[i - 1]][d[i]]);
        }
    }
    double ans = 100000000.0;
    for (int i = 0; i <= m; i++) ans = min(ans, min(f[p][i][0], f[p][i][1]));
    printf("%.2lf\n", ans);
    return 0;
}



CLB
11个月前

很明显是莫反。
含因子1的-含因子2的-含因子3的+含因子6的···

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e4 + 10;
int n, s, p[N], miu[N]; bool v[N];
void get_miu() {
    miu[1] = 1;
    for (int i = 2; i <= 10000; i++) {
        if (!v[i]) p[++s] = i, miu[i] = -1;
        for (int j = 1; j <= s && i * p[j] <= 10000; j++) {
            v[i * p[j]] = 1;
            if (i % p[j] == 0) break;
            miu[i * p[j]] = -miu[i];
        }
    }
}

int sum[N];

LL C(int n, int m) {
    if (n < m) return 0;
    if (!m) return 1;
    double ans = 1.0;
    for (int i = 1; i <= m; i++) ans = 1.0 * ans * (n + 1 - i) / i;
    return (LL)ans;
}

int main() {
    get_miu();
    while (cin >> n) {
        memset(sum, 0, sizeof(sum));
        int m = 0;
        for (int i = 1; i <= n; i++) {
            int x; scanf("%d", &x);
            m = max(m, x);
            for (int j = 1; j * j <= x; j++)
                if (x % j == 0) {
                    sum[j]++;
                    if (j * j != x) sum[x / j]++;
                }
        }
        LL ans = 0;
        for (int i = 1; i <= m; i++)
            ans += 1ll * miu[i] * C(sum[i], 4);
        cout << ans << endl;
    }
    return 0;
}



CLB
11个月前

感觉我的做法很复杂,但是我真的没有其他思路了。。。
题目说要有m个数在原位,其余m-n个都不在
那么这个答案就是组合问题与错排问题的乘积了。
现在我们考虑错排问题,很明显这个问题需要用到容斥原理
假设我们需要求n的错排个数,则有:
$$
P_n-C_n^1 * P_{n-1}+C_n^2 * P_{n-2}-···+(-1)^n*C_n^n * P_0
$$
这条式子是什么意思呢?
$C_n^2 * P_{n-2}$的意思是先选2个数在原位上,其余的都随意排列。
但是这样子是会超时的。
所以我们要考虑化简式子。
$$
C_n^a * P_{n-a} = \dfrac{n!}{a! * (n-a)!} * (n-a)! = \dfrac{n!}{a!}
$$
接下来我们只需要把$n!$提取出来,然后再用数组s记录下$\dfrac{1}{1!} - \dfrac{1}{2!} + \dfrac{1}{3!}···$就可以了。
最后公式就可以变成:
$$
C_n^m * (P_{n-m}-(n-m)! * s[n-m])
$$
然后就可以O(1)计算出结果了

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
void read(int &x) {
    x = 0; int f = 0; char s = getchar();
    while (!isdigit(s)) f |= s=='-', s = getchar();
    while ( isdigit(s)) x = x * 10 + s - 48, s = getchar();
    x = f ? - x : x;
}

typedef long long LL;
const int N = 1e6 + 10;
const LL P = 1e9 + 7;

LL fc[N], inv[N], s[N];

LL power(LL a, LL b) {
    LL ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % P;
        a = a * a % P; b >>= 1;
    }
    return ans;
}

LL C(int n, int m) { return fc[n] * inv[m] % P * inv[n - m] % P; }
LL p(int n) { return fc[n];}
//LL CP(int n, int a) { return fc[n] * inv[a] % P;} // C(n,a) * P(n - a) = n! / a!

int main() {
    fc[0] = 1; inv[0] = 1;
    for (int i = 1; i <= 1000000; i++) 
        fc[i] = fc[i - 1] * i % P, inv[i] = power(fc[i], P - 2);
    for (int i = 1, j = 1; i <= 1000000; i++, j *= -1) 
        s[i] = s[i - 1] + 1ll * j * inv[i] % P, s[i] %= P;
    int T; cin >> T;
    while (T--) {
        int n, m; read(n), read(m);
        LL s1 = fc[n - m] * s[n - m] % P;
        LL s2 = (p(n - m) - s1 + P) % P;
        LL ans = C(n, m) * s2 % P;
        printf("%lld\n", ans);
    }
    return 0;
}



CLB
11个月前

(我被这道题恶心了大半个上午)

这道题是一个带mod的高斯消元,所以很明显不能用double类型的数组求解。

那么我们就需要在高斯消元的时候求出两个数的最小公倍数,然后分别乘上一个数以后相减。

接着依次判断无解,多解和只有一组解的情况,最后在求解的时候用乘法逆元(有一个小细节,就是ax=b时,a和b可能一正一负)或者exgcd。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
const int N = 310, P = 7;
int power(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % P;
        a = a * a % P; b >>= 1;
    }
    return ans;
}
int n, m, a[N][N], ans[N];
map<string, int> mp;

void init() {
    mp["MON"] = 1;
    mp["TUE"] = 2;
    mp["WED"] = 3;
    mp["THU"] = 4;
    mp["FRI"] = 5;
    mp["SAT"] = 6;
    mp["SUN"] = 7;
}

int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a;}

void Prepare() {
    int k, st, ed; string s;
    memset(a, 0, sizeof(a));
    for (int i = 1; i <= m; i++) {
        scanf("%d", &k);
        cin >> s; st = mp[s];
        cin >> s; ed = mp[s];
        a[i][n + 1] = (ed - st + 1 + P) % P;
        for (int j = 1; j <= k; j++) {
            scanf("%d", &st);
            a[i][st]++; a[i][st] %= P;
        }
    }
}

void Guass() {
    int now = 1; bool flag = 0;
    for (int i = 1; i <= n; i++) {
        int k = now;
        for (; k <= m; k++) if (a[k][i] != 0) break;
        if (k == m + 1) continue;
        if (k != now) for (int j = 1; j <= n + 1; j++) swap(a[now][j], a[k][j]);
        for (int j = 1; j <= m; j++) {
            if (j == now) continue;
            if (a[j][i] == 0) continue;
            int t = a[now][i] * a[j][i] / gcd(a[now][i], a[j][i]);
            int p1 = t / a[now][i], p2 = t / a[j][i];
            for (int k = 1; k <= n + 1; k++)
                a[j][k] = (a[j][k] * p2 - a[now][k] * p1) % P;
        }
        if (i == n) flag = 1;
        now++; if (now == m + 1) break;
    }
    for (int i = 1; i <= m; i++) {
        if (a[i][n + 1] == 0) continue;
        bool bk = 0;
        for (int j = 1; j <= n; j++)
            if (a[i][j] != 0) { bk = 1; break;}
        if (!bk) {puts("Inconsistent data."); return;}
    }
    if (!flag) {puts("Multiple solutions."); return;}
    for (int i = 1; i <= n; i++) {
        if (a[i][i] == 0) {puts("Multiple solutions."); return;}
        if (a[i][i] * a[i][n + 1] < 0) {
            if (a[i][i] < 0) a[i][i] = abs(a[i][i]), a[i][n + 1] = abs((a[i][n + 1] % P - P) % P);
            else a[i][n + 1] = (a[i][n + 1] % P + P) % P;
        }
        ans[i] = a[i][n + 1] * power(a[i][i], P - 2) % P;
        if (ans[i] < 3) ans[i] += P;
    }
    for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
    puts("");
}

int main() {
    init();
    while (cin >> n >> m && n && m) {
        Prepare();
        Guass();
    }
    return 0;
}



CLB
11个月前

我在做这道题时还不会二项式定理呢!
想了一会儿,我发现这个式子可以拆成:
(ax+by)(ax+by)…(ax+by)
也就是在每一个括号了面都选一个数,乘起来。
刚好要求的是x^n * b^m前的系数。
然后利用数形结合,就可以将原来的公式变成这个样子:
1
我们要求的是从原点到(n,m)的路径条数,直接用dp即可(跟快的话可以用组合数)

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1010, P = 10007;
int a, b, k, n, m;
int f[N][N];
int main() {
    cin >> a >> b >> k >> n >> m;
    for (int i = 0; i <= n; i++) f[i][0] = 1;
    for (int j = 0; j <= m; j++) f[0][j] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) 
            f[i][j] = (f[i - 1][j] + f[i][j - 1]) % P;
    int ans = f[n][m];
    a %= P;
    for (int i = 1; i <= n; i++) ans = (ans * a) % P;
    b %= P;
    for (int i = 1; i <= m; i++) ans = (ans * b) % P;
    cout << ans << endl; return 0;
}



CLB
11个月前

先令(0/1)表示开关的状态(关/开),那么(按/不按)开关表示为(1/0)
然后就像高斯消元一样,把每一个开关和他相关的开关列出一条式子(n个开关一共就n条),然后把他们变成阶梯形矩阵,从后往前求解。
然后分情况讨论:
1:系数全部为0,但是结果为1,那么无解
2:系数有1,那么该开关的状态肯定是确定的,跳过
3:系数全部为0,结果也为0,那么按不按都可以
讨论完以后向上删除。
做完以后我才发现是可以用一个int来储存一条式子的状态的。。。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 41;
int n;
int a[N], b[N], c[N][N];
int main() {
    int T; cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> b[i];
        int x, y;
        memset(c, 0, sizeof(c));
        while (~scanf("%d%d", &x, &y) && x && y) c[y][x] = 1;
        for (int i = 1; i <= n; i++) c[i][n + 1] = a[i] ^ b[i], c[i][i] = 1;
        for (int ki = 1; ki < n; ki++) {
            int k = ki;
            for(; k <= n && !c[k][ki]; k++);
            if (k == n + 1) continue;
            if (k != ki) for (int i = 1; i <= n + 1; i++) swap(c[ki][i], c[k][i]);
            for (int i = ki + 1; i <= n; i++) {
                if (c[i][ki] == 0) continue;
                for (int j = ki; j <= n + 1; j++)
                    c[i][j] = c[i][j] ^ c[ki][j];
            }
        }
        bool flag = 1;
        int sum = 0;
        for (int i = n; i >= 1; i--) {
            bool bk = 0;
            for (int j = i; j <= n; j++)
                if (c[i][j] == 1) { bk = 1; continue;}
            if (!bk) {
                if (c[i][n + 1] == 1) {flag = 0; break; }
                sum++;
            }
            if (c[i][i] == 0) continue;
            for (int j = i - 1; j >= 1; j--) {
                if (c[j][i] == 0) continue;
                for (int k = i; k <= n + 1; k++)
                    c[j][k] = c[j][k] ^ c[i][k];
            }
        }
        if (!flag) {puts("Oh,it's impossible~!!"); continue;}
        int ans = 1;
        for (int i = 1; i <= sum; i++) ans = ans * 2;
        cout << ans << endl;
    }
    return 0;
}