trang chủ / đề bài / icpc19_reg_c

Đếm số đối xứng

Đề bài

Mô tả

Một số đối xứng (palindrome) là một số nguyên không âm không có chữ số 0 ở đầu, đọc từ trái sang phải hay từ phải sang trái đều như nhau. Ví dụ, 12321, 44 và 9 là các số đối xứng, còn 010, 123 và 100 thì không.

Cho số nguyên dương n, số nguyên tố p và số nguyên không âm k nhỏ hơn p. Một số đối xứng x được gọi là số đối xứng tốt khi và chỉ khi x đồng dư với k theo modulo p. Nói cách khác, số dư khi chia x cho p bằng k.

Hãy đếm số lượng số đối xứng tốt có đúng n chữ số. Vì kết quả có thể rất lớn, hãy in ra kết quả theo modulo 109+7.

Dữ liệu vào

Một dòng gồm ba số nguyên n, p và k (1≤n≤1018, 2≤p≤1000, 0≤k<p). Đảm bảo p là số nguyên tố.

Dữ liệu ra

In ra một số nguyên là số lượng số đối xứng tốt có đúng n chữ số, theo modulo 109+7.

Ràng buộc

  • 1≤n≤1018
  • 2≤p≤1000, p là số nguyên tố
  • 0≤k<p

Ví dụ

Input Output Giải thích
1 2 0 5 Các số đối xứng tốt là 0,2,4,6,8.
2 11 0 9 Ví dụ bổ sung (không có trong đề gốc). Các số đối xứng có 2 chữ số là 11,22,…,99, tất cả đều chia hết cho 11.

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