trang chủ / đề bài / icpc24_nat_g

Phân nhóm tham lam

Đề bài

Mô tả

Cho dãy A gồm n phần tử a1,a2,…,an và một số nguyên k. Hãy chọn một tập các đoạn thỏa mãn:

  • mỗi đoạn gồm các phần tử liên tiếp của A,
  • mỗi đoạn có ít nhất k phần tử,
  • các phần tử trong cùng một đoạn đôi một khác nhau,
  • không có hai đoạn nào chung phần tử, tức là mỗi phần tử của A thuộc tối đa một đoạn.

Nhiệm vụ của bạn là tìm số đoạn lớn nhất có thể chọn, và đếm số cách chọn các đoạn để đạt được số lượng lớn nhất đó.

Hai cách chọn được coi là khác nhau nếu xảy ra một trong hai điều sau:

  • Có một phần tử ai thuộc một đoạn nào đó trong cách này nhưng không thuộc đoạn nào trong cách kia.
  • Có hai phần tử ai và aj thuộc cùng một đoạn trong cách này nhưng thuộc hai đoạn khác nhau trong cách kia.

Để bài toán khó hơn một chút, bạn được cho thêm q số nguyên l1,l2,…,lq. Với mỗi giá trị li, hãy giải bài toán trên với k=li.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test t.

Mỗi bộ test gồm ba dòng:

  • Dòng thứ nhất chứa hai số nguyên n và q (1≤n≤666666, 1≤q≤333).
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (1≤ai≤999999999).
  • Dòng thứ ba chứa q số nguyên l1,l2,…,lq (1≤li≤n).

Dữ liệu đảm bảo tổng n trên tất cả các bộ test không vượt quá 666666, và tổng q trên tất cả các bộ test không vượt quá 666666.

Dữ liệu ra

Với mỗi bộ test, in ra q dòng. Dòng thứ i chứa kết quả của bài toán với k=li, gồm hai số nguyên cách nhau bởi dấu cách:

  • số đoạn lớn nhất có thể chọn,
  • số cách chọn các đoạn để đạt được số lượng lớn nhất đó, lấy modulo 998244353.

Ràng buộc

  • 1≤n≤666666, 1≤q≤333
  • 1≤ai≤999999999, 1≤li≤n
  • Tổng n và tổng q trên tất cả các bộ test đều không vượt quá 666666

Ví dụ

Ký hiệu [l,r] là đoạn gồm các phần tử al,al+1,…,ar.

Input Output Giải thích
2
5 2
1 2 1 2 1
2 3
6 2
1 2 3 4 5 6
3 5
2 3
0 1
2 1
1 3
Bộ test thứ nhất, k=2: chọn được tối đa 2 đoạn, có 3 cách: [1,2] và [3,4]; [1,2] và [4,5]; [2,3] và [4,5]. Với k=3, không có đoạn nào dài ít nhất 3 gồm các phần tử đôi một khác nhau (chỉ có một cách là không chọn gì). Bộ test thứ hai, k=3: cách duy nhất là [1,3] và [4,6]. Với k=5: chỉ chọn được một đoạn, là một trong [1,5], [2,6], [1,6].
1
4 4
1 2 3 1
3 1 4 2
1 2
4 1
0 1
2 1
k=3: một đoạn, [1,3] hoặc [2,4]. k=1: mỗi phần tử là một đoạn. k=4: không chọn được đoạn nào. k=2: chỉ có [1,2] và [3,4].

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0