trang chủ / đề bài / icpc23_nat_b

Xâu ở giữa

Đề bài

Mô tả

Hôm nay, trong môn học thuật toán, Hạnh được học về thứ tự từ điển.

Giáo sư giao cho Hạnh một bài toán đếm: cho hai xâu a, b và một số nguyên l, đếm số xâu c có độ dài l sao cho c lớn hơn a và nhỏ hơn b theo thứ tự từ điển.

Bài toán này khá đơn giản với Hạnh. Bạn ấy viết ngay được hàm countBetween(a, b, l, p) hoạt động như sau:

  • Hàm có bốn tham số: a và b là hai xâu gồm các chữ cái tiếng Anh in thường, l và p là hai số nguyên dương.
  • Hàm đếm chính xác số xâu c gồm đúng l chữ cái tiếng Anh in thường thoả mãn a<c<b theo thứ tự từ điển.
  • Hàm trả về một số nguyên không âm là số dư khi chia số xâu c như vậy cho p.

Để bài toán thú vị và thử thách hơn, giáo sư yêu cầu Hạnh xử lý nhiều truy vấn đếm xâu nằm giữa. Để giải bài toán khó hơn này, Hạnh viết mã giả sau:

function solve(s, w, d, p):
    a = "icpcvn"
    b = "icpcvn"
    res = 0

    for each i from 0 to length(s) - 1:
        if w[i] equals 'A':
            insert character s[i] at the end of string a
        else:
            insert character s[i] at the end of string b

        sum = 0
        for each integer l in d:
            sum += countBetween(a, b, l, p)

        res = res xor (sum % p * (i + 1))

    return res

Hàm solve nhận bốn tham số:

  • Hai xâu s và w có cùng độ dài; s chỉ gồm các chữ cái tiếng Anh in thường, w chỉ gồm các ký tự A và B.
  • d là một dãy các số nguyên dương.
  • p là một số nguyên dương.

Trong mã giả trên, length(s) là số ký tự của xâu s, còn s[i] là ký tự thứ i của xâu s; các ký tự được đánh số từ 0. Phép xor là phép XOR theo bit, và sum % p * (i + 1) được tính là (summodp)·(i+1).

Đáng tiếc, Hạnh nhận ra chương trình của mình có thể chạy quá chậm với một số bộ dữ liệu của giáo sư. Vì vậy, Hạnh nhờ bạn viết chương trình tính nhanh giá trị trả về của hàm trên khi biết giá trị của tất cả các tham số.

Nhắc lại, xâu X=x0x1x2…xm được gọi là nhỏ hơn xâu Y=y0y1y2…yn theo thứ tự từ điển khi và chỉ khi một trong hai điều kiện sau thoả mãn:

  • m<n và xi=yi với mọi 0≤i≤m;
  • tồn tại chỉ số i sao cho i≤min(m,n), xi<yi và xj=yj với mọi 0≤j<i.

Xâu X được gọi là lớn hơn xâu Y theo thứ tự từ điển khi và chỉ khi Y nhỏ hơn X theo thứ tự từ điển.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên q, n và p (1≤q≤2·106, 1≤n≤7·104, 1≤p≤109): độ dài của các tham số s và w, số phần tử của tham số d và giá trị của tham số p.
  • Dòng thứ hai chứa n số nguyên d1,d2,…,dn (1≤di≤109): các phần tử của tham số d.
  • Dòng thứ ba chứa một xâu gồm đúng q chữ cái tiếng Anh in thường: tham số s.
  • Dòng thứ tư chứa một xâu gồm đúng q ký tự A và B: tham số w.

Dữ liệu ra

In ra một số nguyên duy nhất là giá trị trả về của hàm solve ở trên.

Ràng buộc

  • 1≤q≤2·106
  • 1≤n≤7·104
  • 1≤p≤109
  • 1≤di≤109

Ví dụ

Input Output Giải thích
2 3 45
6 7 8
ca
BA
25 Ban đầu a=b= icpcvn. Khi i=0: a= icpcvn, b= icpcvnc; có 0 xâu độ dài 6, 2 xâu độ dài 7 (icpcvna, icpcvnb) và 52 xâu độ dài 8 (icpcvnaa tới icpcvnbz) nằm giữa, 52mod45=7, nên sum=9 và res=9. Khi i=1: a= icpcvna, b= icpcvnc; các giá trị lần lượt là 0, 1 (icpcvnb) và 52mod45=7, nên sum=8 và res=9⊕16=25.
5 5 1000000000
7 8 9 8 1000000000
zbbaa
BBAAB
6279498621 Ví dụ bổ sung. Ở mọi bước a<b: sau hai bước đầu a= icpcvn là tiền tố của b= icpcvnzb, sau đó a bắt đầu bằng icpcvnb còn b bắt đầu bằng icpcvnz.

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