Bạn có \(n\) đoạn thẳng nằm trong \([1,m]\). Đoạn thứ \(i\) (\(0\le i<n\)) là \([l_i,r_i]\).

Với mỗi tập chỉ số \(S\subseteq\{0,1,\ldots,n-1\}\), dựng một đồ thị có tập đỉnh là \(S\). Hai đỉnh \(u,v\) được nối bởi một cạnh khi và chỉ khi hai đoạn tương ứng giao nhau, tức tồn tại \(x\in[1,m]\) sao cho

Tập \(S\) được gọi là đẹp khi đồ thị vừa dựng chính xác là một cây.

Cho số nguyên dương \(k\le n\). Với mỗi \(s=1,2,\ldots,k\), hãy đếm số tập đẹp có đúng \(s\) phần tử. In các kết quả theo modulo \(998\,244\,353\).

Yêu cầu cài đặt

Bạn không được cài đặt hàm main. Submission phải include segment.h và cài đặt đúng hai hàm sau:

void init(int c, int t);

• c là số hiệu test; c = 0 biểu thị dữ liệu mẫu.
• t là số bộ dữ liệu trong test này.
• Bộ chấm gọi hàm đúng một lần khi chương trình bắt đầu.

std::vector<int> segment(
    int n, int m, int k,
    std::vector<int> l,
    std::vector<int> r
);

• n, m, k có ý nghĩa như trong đề.
• l, r chứa hai đầu mút của \(n\) đoạn theo thứ tự.
• Hàm phải trả về một vector có đúng \(k+1\) phần tử \(a\), trong đó \(a_0=0\) và \(a_s\) là đáp án cho kích thước \(s\), lấy modulo \(998\,244\,353\).
• Bộ chấm gọi hàm đúng t lần.

Khung khai báo:

#include "segment.h"

Dữ liệu bộ chấm

Grader đọc dữ liệu theo định dạng sau:

• Dòng đầu chứa \(c,t\).
• Với mỗi trong \(t\) bộ dữ liệu:
• Dòng đầu chứa \(n,m,k\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(l_i,r_i\).

Với mỗi bộ dữ liệu, grader ghi một dòng gồm \(a_1,a_2,\ldots,a_k\).

Ràng buộc

Gọi \(K\) là tổng các giá trị \(k\) trong một test.

• \(1\le t\le20\).
• \(1\le n\le3000\).
• \(1\le m\le10^3\).
• \(1\le k\le n\) và \(K\le200\).
• \(1\le l_i\le r_i\le m\).

Phân nhóm

Mỗi test có giá trị \(4\) điểm.

• Tính chất A: với mọi \(i\ne j\), đoạn \(i\) không chứa đoạn \(j\), tức \(l_i>l_j\) hoặc \(r_i<r_j\).
• Tính chất B: với mọi \(0\le i<j<n\), đoạn \(i\) chứa đoạn \(j\) hoặc hai đoạn không giao nhau; tức \(l_i\le l_j\le r_j\le r_i\), hoặc \(r_i<l_j\), hoặc \(l_i>r_j\).
• Tính chất C: toàn bộ \(2n\) đầu mút \(l_0,\ldots,l_{n-1},r_0,\ldots,r_{n-1}\) đôi một khác nhau.

Ví dụ

0 3
3 3 3
1 2
2 3
1 3
4 5 4
1 2
2 3
3 4
4 5
4 2 3
1 2
1 2
1 2
1 1

3 3 0
4 3 2 1
4 6 0

Trong bộ đầu tiên, ba tập một phần tử và ba tập hai phần tử đều đẹp. Tập ba phần tử tạo thành tam giác nên không đẹp.

Trong bộ thứ hai, số tập đẹp theo kích thước lần lượt là \(4,3,2,1\).

Nguồn

CCF NOI 2026 - Ngày 1, bài Segment. Đề và dữ liệu chính thức được phát hành theo giấy phép CC BY-NC.