trang chủ / đề bài / bearpoly

Đổi một hệ số

Đề bài

Mô tả

Một đa thức P(x)=a0+a1x+a2x2+…+anxn được gọi là hợp lệ nếu nó có bậc đúng bằng n và các hệ số là số nguyên có trị tuyệt đối không vượt quá k, tức là:

  • ai là số nguyên với mọi i;
  • |ai|≤k với mọi i;
  • an≠0.

Cho một đa thức hợp lệ P với các hệ số a0,a1,…,an, biết rằng P(2)≠0. Bạn cần thay đổi đúng một hệ số của P để thu được một đa thức hợp lệ Q bậc n thỏa mãn Q(2)=0.

Hãy đếm số cách làm như vậy. Hai cách được coi là khác nhau nếu hai đa thức Q thu được có hệ số khác nhau.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n và k: bậc của đa thức và giới hạn trị tuyệt đối của các hệ số.
  • Dòng thứ hai chứa n+1 số nguyên a0,a1,…,an: các hệ số của P.

Dữ liệu ra

In ra một số nguyên: số cách thay đổi một hệ số để thu được đa thức hợp lệ Q với Q(2)=0.

Ràng buộc

  • 1≤n≤2·105
  • 1≤k≤109
  • |ai|≤k, an≠0
  • P(2)≠0

Ví dụ

Input Output Giải thích
3 1000000000
10 -9 -3 5
3 P(2)=10−18−12+40=20. Có ba cách: đặt a0=−10, đặt a1=−19, hoặc đặt a2=−8.
3 12
10 -9 -3 5
2 Cùng đa thức như trên, nhưng cách đặt a1=−19 không còn hợp lệ vì |−19|>12.
2 20
14 -7 19
0 P(2)=14−14+76=76. Đổi a0 phải thành −62, đổi a1 phải thành −45, đều vượt quá k; còn đổi a2 thì cần a2=0, khi đó bậc không còn bằng 2.

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