trang chủ / đề bài / icpc22_reg_h

Bài khó nhất

Đề bài

Mô tả

Cho hai số nguyên n và d (1≤d≤n). Định nghĩa f(k) là số hoán vị của 1,2,…,n thỏa mãn:

  • số nghịch thế của hoán vị bằng k;
  • khi xóa khỏi hoán vị mọi phần tử có giá trị lớn hơn hẳn d, các phần tử còn lại được sắp xếp tăng dần.

Hãy tính f(k) theo modulo 998244353 với mọi k từ 1 tới min(250000,n(n−1)2).

Hoán vị là một mảng gồm n số nguyên phân biệt từ 1 tới n theo thứ tự tùy ý. Ví dụ, [2,3,1,5,4] là một hoán vị, nhưng [1,2,2] không phải hoán vị (2 xuất hiện hai lần) và [1,3,4] cũng không phải hoán vị (n=3 nhưng mảng chứa số 4).

Một nghịch thế của hoán vị p là một cặp (i,j) (1≤i<j≤|p|) sao cho pi>pj.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên n và d (2≤n≤106, 1≤d≤n).

Dữ liệu ra

In ra min(250000,n(n−1)2) dòng. Dòng thứ k chứa f(k) modulo 998244353.

Ràng buộc

  • 2≤n≤106
  • 1≤d≤n

Ví dụ

Input Output Giải thích
2 1 1 Có hai hoán vị độ dài 2 là {1,2} và {2,1}. {2,1} là hoán vị duy nhất có 1 nghịch thế.
5 3 2
3
4
4
3
2
1
0
0
0
k=1: {1,2,3,5,4}, {1,2,4,3,5}. k=2: {1,2,4,5,3}, {1,2,5,3,4}, {1,4,2,3,5}. k=3: {1,2,5,4,3}, {1,4,2,5,3}, {1,5,2,3,4}, {4,1,2,3,5}. k=4: {1,4,5,2,3}, {1,5,2,4,3}, {4,1,2,5,3}, {5,1,2,3,4}. k=5: {1,5,4,2,3}, {4,1,5,2,3}, {5,1,2,4,3}. k=6: {4,5,1,2,3}, {5,1,4,2,3}. k=7: {5,4,1,2,3}. Với k=8,9,10 không có hoán vị nào thỏa mãn.

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