33OJ
登录 注册

#P17617. [Math+Girl×1] QuomodocunquizE / A+B>C Problem

[Math+Girl×1] QuomodocunquizE / A+B>C Problem

背景

$\color{white}\small 93^{\text{rd}}\text{ Problem by ArC.}$

题目描述

给定 NN。以下我们称长为 NN 的排列构成的三元组 (A,B,C)(A,B,C) 为排列三元组。

对于一个排列三元组 (A,B,C)(A,B,C),我们如下定义它的权值:

  • 设 GG 是一张 NN 个点 NN 条边的无向图,其第 ii 条边为 (Ai,Bi)(A_i,B_i)。(A,B,C)(A,B,C) 的权值为 GG 的连通块数。

注意排列三元组的权值与 CC 无关。


设 SS 是满足以下条件的排列三元组的集合。

  • ∀1≤i≤N,Ai+Bi>Ci\forall 1\leq i\leq N,A_i+B_i>C_i.
  • 此外,我们会额外给出 M1+M2M_1+M_2 条限制。
    • M1M_1 条第一类限制形如:对于任意的 ii,若 ⌈N+Ai2⌉=a\left\lceil\frac{N+A_i}2\right\rceil=a,则 Ci≠cC_i\neq c。
    • M2M_2 条第二类限制形如:对于任意的 ii,若 Bi=bB_i=b,则 Ci≠cC_i\neq c。

设 S0S_0 是 SS 中权值为偶数的元素个数,S1S_1 是 SS 中权值为奇数的元素个数,你需要求 S0−S1S_0-S_1。答案对 119×223+1119\times 2^{23}+1 取模。

输入格式

本题多测。第一行一个整数 TT,代表数据组数。接下来 TT 组数据。

对于每一组数据,第一行三个整数 N,M1,M2N,M_1,M_2。

接下来 M1M_1 行,每行两个整数 a,ca,c,代表一条第一类限制。

接下来 M2M_2 行,每行两个整数 b,cb,c,代表一条第二类限制。

输出格式

输出 TT 行,每行一个整数,分别代表每组数据的答案。

7
3 1 1
3 2
2 2
3 1 1
2 2
2 2
4 1 1
3 2
3 2
2 0 0
6 8 8
4 3
6 3
4 6
5 2
5 4
5 6
6 2
6 5
5 1
1 5
6 1
5 2
5 6
2 6
4 2
4 3
7 8 8
1 7
2 6
3 5
5 3
5 4
7 3
6 2
7 2
5 1
6 1
5 2
4 2
3 7
5 7
4 3
7 4
5 5 10
5 1
5 3
5 4
4 1
4 5
1 2
1 3
2 4
2 5
3 3
3 5
4 1
4 2
5 2
5 4
6
998244347
24
998244351
720
10080
0

提示

样例解释

第一组数据中 N=3N=3。一组符合限制的排列三元组 (A,B,C)(A,B,C) 是 ((2,3,1),(2,1,3),(1,3,2))((2,3,1),(2,1,3),(1,3,2)),其对应的图 GG 为 (2,2),(3,1),(1,3)(2,2),(3,1),(1,3),有 22 个连通块,于是这个三元组的权值是 22。

可以暴力枚举得到答案为 66。

注意 ((1,2,3),(1,2,3),(1,2,3))((1,2,3),(1,2,3),(1,2,3)) 是不合法的,因为 B2=2,C2=2B_2=2,C_2=2 不满足 b=2,c=2b=2,c=2 的限制。

数据范围与约定

本题开启捆绑测试。

::cute-table{tuack}

子任务 T≤T\leq 特殊限制 分值
11 1010 N≤6N\leq 6 55
22 ^ M1=0M_1=0 1010
33 M2=0M_2=0
44 10410^4 ∑N2≤1002\sum N^2\leq 100^2 2020
55 ^ ∑N2≤5002\sum N^2\leq 500^2 3030
66 - 2525

对于所有数据:

  • 1≤T≤1041\leq T\leq 10^4;
  • 2≤N≤15002\leq N\leq 1500;
  • ∑N2≤15002\sum N^2\leq 1500^2;
  • 0≤M1,M2≤N20\leq M_1,M_2\leq N^2;
  • ∑(M1+M2)≤6×105\sum (M_1+M_2)\leq 6\times 10^5;
  • 1≤a,b,c≤N1\leq a,b,c\leq N。