Wonderful

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Prototype, uou
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 2400 Thời gian: 5.0s Bộ nhớ: 1G Input: wonderful.inp Output: wonderful.out

Wonderful

Cho một hoán vị \(p\) của các số nguyên từ \(1\) đến \(n\). Bạn được thực hiện thao tác sau một số lần:

  • Chọn một số nguyên \(i\) thỏa mãn \(1 \le i \le n - 1\)
  • Và đổi giá trị của hai phần tử \(p_i\) và \(p_{i+1}\) cho nhau.

Một hoán vị \(q\) được gọi là tuyệt vời nếu \(q_i \ne i\) với mọi số nguyên \(i\) thỏa mãn \(1 \le i \le n\).

Gọi \(f(p)\) là số thao tác tối thiểu cần phải thực hiện để chuyển đổi hoán vị \(p\) thành một hoán vị tuyệt vời.

Yêu cầu: Hãy tính tổng của \(f(p)^2\) với mọi hoán vị \(p\) có thể. Vì tổng này có thể rất lớn, nên hãy in ra phần dư của đáp án khi chia cho \(998244353\).

Input

  • Vào từ tệp văn bản WONDERFUL.INP một số nguyên \(n\) là độ dài của hoán vị \(p\).
  • Ràng buộc: \(2 \le n \le 2 \cdot 10^5\).

Output

  • Ghi ra tệp văn bản WONDERFUL.OUT là phần dư của đáp án khi chia cho \(998244353\).

Example

Test 1

Input 
3
Output 
7
Note

Với \(n = 3\) thì ta có \(6\) hoán vị là \((1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)\). Số thao tác tối thiểu để chuyển các hoán vị tương ứng trên thành hoán vị tuyệt vời là \(2, 1, 1, 0, 0, 1\). Tổng các \(f(p)^2\) là \(2^2 + 1^2 + 1^2 + 0^2 + 0^2 + 1^2 = 7\).

Test 2

Input 
4
Output 
27

Test 3

Input 
101206
Output 
160323547

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: