Bịp

Xem PDF
Tác giả:
dang7rickroll , stack_queue_4977
Dạng bài
Điểm: 50 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Minh rất thích lập trình, hôm nay anh ấy gặp một bài toán có độ khó 3501 codeforces như sau:
Cho \(3\) số nguyên dương \(n,l,r\). Nhiệm vụ của bạn là đếm số cặp dãy số \(a\) và \(b\) độ dài \(n\) sao cho thỏa mãn ba điều kiện sau:

  • \(max(max(a),max(b))\le r\) với (max(\(a\)) là số lớn nhất trong dãy \(a\)).
  • \(min(min(a),min(b))\ge l\) với (min(\(a\)) là số nhỏ nhất trong dãy \(a\)).
  • \(a_1\times a_2...\times a_n=b_1\times b_2...\times b_n\)

Input, Output và Subtasks

Input
  • Dòng đầu tiên là số nguyên \(q\) thể hiện số test (\(q\le5\)).
  • \(q\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương \(n,l,r\) (\(1\le l,r,n\le 10^6\)).
Output
  • Với mỗi testcase, ịn ra kết quả trên 1 dòng, nếu số lượng dãy thỏa mãn nhỏ hơn \(998244353\) thì in kết quả theo modulo \(998244353\), ngược lại thì in ra \(-1\)
Subtasks
  • Subtask \(1\):(\(10\%\)) \(n=1\).
  • Subtask \(2\):(\(10\%\)): \(n\leq 10,r-l\leq 6\)
  • Subtask \(3\):(\(20\%\)) \(n,l,r\leq 100\).
  • Subtask \(4\): (\(30\%\)) \(n,l,r\leq 1000\).
  • Subtask \(5\): (\(30\%\)) không có giới hạn gì thêm.

Sample input

2
1 1 1
123456 1 69420

Sample output

1
-1

Bình luận