Lớp Bùa Chú

Đề bài

Mô tả

Trong lớp Bùa Chú của giáo sư Flitwick, các học sinh luyện tập một chuỗi n phép thuật. Mỗi phép thuật có một chỉ số năng lượng phép thuật ai (có thể âm, dương hoặc bằng 0). Một phép thuật có năng lượng âm nghĩa là phép đó hút năng lượng từ môi trường xung quanh.

Giáo sư Flitwick muốn tìm số lượng đoạn con liên tiếp của chuỗi phép thuật sao cho tổng năng lượng phép thuật trong đoạn đó bằng đúng K.

Một đoạn con liên tiếp là một dãy các phần tử liền kề al,al+1,…,ar với 1≤l≤r≤n.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n và K — số lượng phép thuật và tổng năng lượng cần tìm.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an — chỉ số năng lượng của mỗi phép thuật.

Dữ liệu ra

  • In ra một số nguyên duy nhất — số lượng đoạn con liên tiếp có tổng bằng K.

Ràng buộc

  • 1≤n≤2×105
  • −109≤K≤109
  • −109≤ai≤109

Ví dụ

Input Output Giải thích
5 5
1 2 3 4 5
2 Có 2 đoạn con có tổng bằng 5: đoạn [2,3] (tổng 2+3=5) và đoạn [5] (tổng 5).
7 3
3 -1 2 -1 3 -1 2
6 Có 6 đoạn con có tổng bằng 3: [3] (vị trí 1), [3,−1,2,−1] (vị trí 1-4), [−1,2,−1,3] (vị trí 2-5), [2,−1,3,−1] (vị trí 3-6), [−1,3,−1,2] (vị trí 4-7), và [3] (vị trí 5).

Ghi chú

  • Kết quả có thể rất lớn, cần dùng kiểu dữ liệu 64-bit.

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