Đề bài

Cho một hoán vị

của các số \(1,2,\ldots,n\). Một phép tách của \(p\) là một hoán vị \(q\) có thể thu được bằng quy trình sau:

1. Chọn hai tập chỉ số \(A=\{i_1,i_2,\ldots,i_k\}\) và \(B=\{j_1,j_2,\ldots,j_l\}\) sao cho \(A\cap B=\varnothing\), \(A\cup B=\{0,1,\ldots,n-1\}\), \(i_1<i_2<\cdots<i_k\) và \(j_1<j_2<\cdots<j_l\).
2. Tạo hoán vị

Ký hiệu \(S(p)\) là tập hợp tất cả các phép tách của hoán vị \(p\).

Cho số nguyên \(n\) và một tập \(T\) gồm \(m\) hoán vị độ dài \(n\). Hãy đếm số hoán vị \(p\) độ dài \(n\) thỏa mãn

Vì kết quả có thể rất lớn, hãy trả về kết quả theo modulo \(998\,244\,353\).

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

int solve(
    int n,
    int m,
    std::vector<std::vector<int>>& splits
);

• n: độ dài của mỗi hoán vị.
• m: số phép tách được cho.
• splits: mảng gồm \(m\) hoán vị đôi một phân biệt, chính là các phần tử của tập \(T\).
• Hàm phải trả về số hoán vị \(p\) có thể có, theo modulo \(998\,244\,353\).
• Hàm được gọi đúng một lần cho mỗi bộ kiểm thử.

Ràng buộc

• \(1\le n\le300\).
• \(1\le m\le300\).

Phân nhóm

• Phân nhóm 1 (6 điểm): \(m=1\).
• Phân nhóm 2 (7 điểm): \(1\le n,m\le10\).
• Phân nhóm 3 (17 điểm): \(1\le n,m\le18\).
• Phân nhóm 4 (17 điểm): \(1\le n\le30\), \(1\le m\le15\).
• Phân nhóm 5 (16 điểm): \(1\le n,m\le90\).
• Phân nhóm 6 (16 điểm): \(1\le n\le300\), \(1\le m\le15\).
• Phân nhóm 7 (21 điểm): Không có ràng buộc bổ sung.

Ví dụ

solve(3, 2, {{1, 2, 3}, {2, 1, 3}})

4

123
132
213
231

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): n m.
• Dòng \(2+i\) với \(0\le i<m\): splits[i][0] splits[i][1] ... splits[i][n-1].

Trình chấm mẫu in kết quả của lời gọi solve với các tham số tương ứng.