trang chủ / đề bài / icpc23_reg_i

Đến giờ đấu bài rồi!

Đề bài

Mô tả

Tên các nhân vật đã được che đi vì lý do bản quyền.

Ka•ba S•to, giám đốc của Ka•baCorp và là Duelist số một Nhật Bản, lại một lần nữa chuẩn bị đánh bại đối thủ truyền kiếp M•to Y•gi. Đã nếm hết thất bại này đến thất bại khác, phần lớn nhờ "hào quang nhân vật chính" của Y•gi, lần này Ka•ba quyết định bỏ qua vẻ cao thượng thường ngày và tự mình dùng thủ đoạn.

Anh ta yêu cầu cả hai người chơi đấu bằng Duel Disk++ mới phát triển, thiết bị có khả năng tự động xáo bài. Là người phát minh ra Duel Disk++, Ka•ba biết chính xác cơ chế xáo bài hoạt động thế nào. Giả sử bộ bài của người chơi có n lá. Sau một lần xáo, thiết bị chuyển lá bài đang ở vị trí thứ i tới vị trí thứ pi (các vị trí được đánh số từ 1 đến n tính từ trên xuống), trong đó p là một hoán vị của các số nguyên từ 1 đến n, riêng cho từng thiết bị. Từ kinh nghiệm trước đây, Ka•ba biết Y•gi luôn xếp bộ bài theo một thứ tự nhất định, và Y•gi luôn dùng thiết bị xáo bài đúng k lần khi bắt đầu trận đấu. Để giành chiến thắng, Ka•ba cần lá bài thứ i trong cách xếp ban đầu của Y•gi nằm ở vị trí thứ ai sau k lần xáo. Để chắc chắn điều đó, Ka•ba sẽ bí mật thay đổi hoán vị p trong Duel Disk++ của Y•gi trước trận đấu.

Cho n số nguyên a1,a2,…,an và số lần xáo k, hãy giúp Ka•ba đếm số hoán vị p thoả mãn yêu cầu.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và k (1≤n≤105, 1≤k<10100): số lá bài trong bộ bài của Y•gi và số lần Y•gi xáo bộ bài ban đầu.

Dòng thứ hai chứa n số nguyên đôi một khác nhau a1,a2,…,an (1≤ai≤n): cách sắp xếp bộ bài mong muốn.

Dữ liệu ra

In ra một số nguyên: số hoán vị p mà Ka•ba có thể chọn để đạt mục đích, lấy phần dư khi chia cho 998244353.

Ràng buộc

  • 1≤n≤105
  • 1≤k<10100
  • a là một hoán vị của 1,2,…,n.

Ví dụ

Input Output Giải thích
5 2
2 4 3 1 5
2 Ka•ba có thể chọn p=[4,1,5,2,3] hoặc p=[4,1,3,2,5].
6 120
1 2 3 4 5 6
720 Có thể chứng minh rằng với mọi p, bộ bài luôn trở về trạng thái ban đầu sau 120 lần xáo, nên cả 6!=720 hoán vị đều thoả mãn.
6 120
1 2 3 4 6 5
0 Như ví dụ trên, sau 120 lần xáo bộ bài luôn trở về trạng thái ban đầu, nên không có hoán vị nào thoả mãn.
10 15
4 8 5 1 3 10 9 2 7 6
465

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