Độ bá đạo của đội hình.

View as PDF

Submit solution

Points: 1.67 (partial)
Time limit: 6.75s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VOS Round 30 - Mạnh Tiến & Anh Khoa
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Hằng năm cứ vào khoảng cuối tháng 10, hai trườnng trung học danh tiếng nhất ở nước Alphabet, trường XYZ và trường ABC, sẽ tổ chức giải bóng chuyền với mục đích tạo ra sân chơi lành mạnh giữa các học sinh của hai trường và cũng là dịp để các học sinh tìm hiểu kỹ hơn về trường bạn. Vì sân vận động rất lớn nên mỗi đội có tới ~N~ người chơi. Trường XYZ là một trường chuyên về các môn tự nhiên còn trường ABC là trường chuyên về các môn xã hội. Để chuẩn bị chiến thuật cho giải đấu sắp tới, trường XYZ cần phải biết mức độ bá đạo của đội bên kia. Nhờ quen biết rộng nên trường XYZ đã biết được chỉ số trung bình các thí sinh sắp tới sẽ chơi cho đội của trường ABC. Độ bá đạo của của một đội bóng chuyền sẽ có giá trị bằng tổng độ bá đạo của các thành viên trong đội và lấy phần dư trong phép chia cho ~BASE~ trong đó độ bá đạo của mỗi thành viên sẽ bằng lũy thừa bậc ~Q~ của chỉ số trung bình của thành viên đó. Biết rằng Q có dạng là ~k^{T}~ .

Yêu cầu: Tính độ bá đạo của đội bóng trường ABC.

Input

  • Dòng đầu chứa số ~N~, ~k~, ~T~, ~BASE~ trong đó ~N \le 10^{7}~, ~k \le 50~, ~T \le 10^{5}~, ~BASE \le 10^{12}~.

  • Dòng tiếp theo chứa ~2~ số nguyên dương là mul và seed.

  • Lưu ý: ~30\%~ số test ~T \le 5~ ~0~.

  • Nguyên tắc sinh dãy ~A~ với ~A_{i}~ là chỉ số trung bình của thành viến thứ ~i~ như sau:

    • ~A_{1} = (mul \times seed + seed) \bmod maxC~.
    • ~A_{i} = (A_{i-1} \times mul + seed) \bmod maxC~.
    • ~a \bmod b~ là phép lấy phần dư của phép chia ~a~ cho ~b~.
    • ~0 \le mul, seed \le 10^{6}~.
    • ~maxC = 2 ^ {20}~

Output

  • Gồm một dòng chứa mốt số nguyên là kết quả bài toán.

Sample Input

4 2 2 89133
3 6

Sample Output

50886

Comments

Please read the guidelines before commenting.


There are no comments at the moment.