Bài tập về nhà vui vẻ

Xem PDF
Tác giả:
longvu
Dạng bài
Điểm: 600 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trên trường, longvu vừa được học về xác xuất và thầy của cậu đã giao rất nhiều bài tập cho cậu. Tuy nhiên cậu đã nhanh chóng hoàn thành gần hết bài tập. Nhưng còn đúng một bài mà cậu nghĩ mãi vẫn chưa ra.

Đề bài như sau:

Cho n hộp quà \(1, 2, 3, ..., n\) xếp trên 1 hàng và trong mỗi hộp có chứa 1 số nguyên \(p_1, p_2, p_3, ..., p_n\) có giá trị từ 1 đến n và các \(p_i\) đôi một phân biệt. Ban đầu các hộp quà được xáo ngẫu nhiên và không biết được con số trong mỗi hộp quà. Có n lượt chọn các hộp quà, trong lượt thứ i nếu chọn hộp quà thứ j thì số điểm nhận được sẽ là \(|pj - i|\) và sau đó loại đi hộp quà thứ j và con số trong hộp quà đó. Như vậy tổng điểm nhận được sau khi kết thúc là tổng điểm của các lần chọn hộp quà.

Tính xác suất để được số điểm sau khi kết thúc là k.

Biết được tài năng của các lập trình viên trên LQDOJ nên longvu muốn nhờ các bạn giải giúp bài tập này nhé.

Input

  • Dòng đầu chứa số nguyên \(t\) - Là số lượng các truy vấn \((1 \leq t \leq 10^5)\).

  • \(t\) dòng tiếp theo chứa số nguyên \(n, k\) \((1 \leq n \leq 100, 0 \leq k \leq n * n)\).

Output

  • In ra kết quả bài toán mod 1234567891 (Đây là 1 số nguyên tố).

Example

Test 1

Input 
4
3 2
44 350
50 1252
39 14
Output 
823045261
582343325
0
464747120
Note

Trong testcase đầu tiên có 2 trường hợp thoả mãn yêu cầu đề bài đó là:

  • Trường hợp 1:

    • Lượt số 1 chọn được hộp có con số là 2 và số điểm nhận được là \(|2 - 1|\) = 1.

    • Lượt số 2 chọn được hộp có con số là 1 và số điểm nhận được là \(|1 - 2|\) = 1.

    • Lượt số 3 chọn được hộp có con số là 3 và số điểm nhận được là \(|3 - 3|\) = 0.

    Số điểm nhận được khi kết thúc là sẽ là 1 + 1 + 0 = 2.

  • Trường hợp 2:

    • Lượt số 1 chọn được hộp có con số là 1 và số điểm nhận được là \(|1 - 1|\) = 0.

    • Lượt số 2 chọn được hộp có con số là 3 và số điểm nhận được là \(|3 - 2|\) = 1.

    • Lượt số 3 chọn được hộp có con số là 2 và số điểm nhận được là \(|2 - 3|\) = 1.

    Số điểm nhận được khi kết thúc là sẽ là 0 + 1 + 1 = 2.

Và có tổng cộng 6 trường hợp có thể xảy ra.

Vậy xác xuất là 2 / 6.

Bình luận