trang chủ / đề bài / icpc20_nat_e

Số học dễ

Đề bài

Mô tả

Harry đang là học sinh năm ba tại Trường Phù thủy và Pháp sư Hogwarts. Trái với suy nghĩ của nhiều người, số học (trong thế giới phù thủy gọi là Số học huyền bí) rất quan trọng để trở thành một phù thủy giỏi.

Trong bài tập về nhà hôm nay, Harry được cho một biểu thức rất dài s có độ dài n, gồm các chữ số và các phép toán +, -. Ký tự thứ i (1≤i≤n) của s được ký hiệu là si.

Harry phải trả lời q truy vấn thuộc một trong hai loại:

  1. ? l r: tính giá trị của biểu thức gồm các ký tự từ thứ l đến thứ r của s (tính cả hai đầu). Vì giá trị này có thể rất lớn, Harry cần tính nó theo modulo 998244353.
  2. ! i c: thay si bằng ký tự c.

Hãy giúp Harry!

Dữ liệu vào

  • Dòng đầu tiên chứa n ký tự là biểu thức s (1≤n≤105). Mọi ký tự đều là chữ số hoặc một trong hai phép toán +, -, và không có hai ký tự liên tiếp nào cùng là phép toán.
  • Dòng thứ hai chứa q (1≤q≤105).
  • q dòng tiếp theo, mỗi dòng chứa một truy vấn:
    • ? l r (1≤l≤r≤n): truy vấn loại thứ nhất. Đảm bảo sr là một chữ số.
    • ! i c (1≤i≤n, c là một chữ số hoặc + hoặc -): truy vấn loại thứ hai. Đảm bảo sau truy vấn này không có hai ký tự liên tiếp nào cùng là phép toán.

Dữ liệu ra

Với mỗi truy vấn loại thứ nhất, in ra giá trị của biểu thức theo modulo 998244353.

Ràng buộc

  • 1≤n≤105, 1≤q≤105.
  • 1≤l≤r≤n, sr là chữ số; 1≤i≤n.

Ví dụ

Input Output Giải thích
123-456+789
10
? 2 5
? 7 9
? 4 6
! 1 +
! 4 0
? 1 7
! 1 -
? 1 3
? 4 7
? 4 5
19
13
998244308
230456
998244330
456
4
Các biểu thức lần lượt là 23−4=19, 6+7=13, −45, +230456, −23, 0456=456 và 04=4. Biểu thức có thể bắt đầu bằng một phép toán (dấu của số đầu tiên) và các số có thể có chữ số 0 ở đầu.
-007+15
6
? 1 4
? 2 7
! 5 -
? 1 7
! 1 9
? 1 4
998244346
22
998244331
9007
Ví dụ bổ sung (không có trong đề gốc). Các biểu thức lần lượt là −007=−7, 007+15=22, −007−15=−22 và 9007.

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