trang chủ / đề bài / icpc21_mb_l

Đếm tập con

Đề bài

Mô tả

Cho dãy số nguyên a1,a2,…,an. Hãy đếm số tập S thỏa mãn đồng thời các điều kiện sau:

  • S⊂{1,2,…,n};
  • ∃x∈S:ax∉S;
  • ∃y∈S:(∀x∈S:ax≠y).

Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho 998244353.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test gồm hai dòng:

  • Dòng đầu tiên chứa số nguyên n (1≤n≤105).
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (1≤|ai|≤n).

Dữ liệu vào kết thúc bằng một dòng chứa duy nhất số 0 (không phải một bộ test). Tổng các giá trị n của mọi bộ test không vượt quá 106.

Dữ liệu ra

Với mỗi bộ test, in ra kết quả trên một dòng.

Ràng buộc

  • 1≤n≤105.
  • 1≤|ai|≤n (các ai có thể âm).
  • Tổng các giá trị n không vượt quá 106.

Ví dụ

Input Output Giải thích
3
1 2 3
3
2 3 1
0
0
6
Ở bộ test thứ nhất, với mọi tập S, mọi x∈S đều có ax=x∈S, nên không tập nào thỏa mãn. Ở bộ test thứ hai, có 6 tập thỏa mãn: {1}, {2}, {3}, {1,2}, {2,3}, {3,1}.
4
2 -1 1 3
0
15 Ví dụ bổ sung (không có trong đề gốc). Mọi tập khác rỗng đều thỏa mãn: 15 tập.

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