Giải 2 dấu sigma
Xem PDFTừ sau cái hôm làm bánh cho ông nguyenminhhai021009 ấy (xem lại bài Bán Bánh Dày), dù tôi kiếm được nhiều tiền nhưng lại bị mất kha khá khách (do bữa đó chỉ lo làm bánh cho ổng thôi mà). Mấy hôm sau, tôi có nhận được tin nhắn của ổng: "Hãy đến địa chỉ này gặp tôi" cùng với địa chỉ lạ. Tôi tới nơi thì, chao ôi, đó là một công ty lớn chuyên về ngành Toán học tên Mathtics. Tôi thấy ông Hải đứng ngoài cửa công ty rôi vẫy tay gọi tôi vào. Hóa ra, ông là Phó Giám Đốc của công ty này, vì nghe đồn tôi là người rất giỏi Toán nên tới thử tài. Vì tôi đã thỏa mãn được yêu cầu của ông lúc đó nên được gọi đến để phỏng vấn vào chức vụ Trợ lí của ngài Giám Đốc Công Ty stack_queue_4977. Tôi được đưa vào phòng của ngài, ngồi xuống ghế trước mặt ngài ấy. Ngài ấy bảo rằng ông rất ấn tượng về việc tôi hoàn thành thử thách của vị Phó Giám Đốc kia, và bảo nếu tôi trả lời chính xác \(Q\) câu hỏi toán mà ông sắp đưa cho tôi đây, thì ông sẽ tuyển dụng tôi ngay, khỏi bàn cãi. Tôi nhận đề, trên đề ghi như sau:
"Cho \(Q\) truy vấn, mỗi truy vấn gồm 2 số \(n\) và \(k\). Tính \(P^k_n\) \(\text{mod}\) \(10^{18}\) biết:"
"Ôi trời ơi khó quá!!!" - Tôi than ở trong đầu. Tôi chưa từng thấy bài thi nào khó như vậy. Tôi đang khổ sở thì nhớ ra các bạn coder LQDOJ. Các bạn ơi, các bạn hãy giải giúp tôi bài thi này để tôi được tuyển dụng nhé. Cảm ơn các bạn rất nhiều!!!!
Input
-
Dòng 1 gồm số \(Q\).
-
\(Q\) dòng tiếp theo, mỗi dòng gồm 2 số \(n\) và \(k\).
Output
- Với mỗi truy vấn, in ra \(P^k_n\) \(\text{mod}\) \(10^{18}\).
Scoring
-
Subtask \(1\) (\(40\%\) số điểm): \(1\le Q \le 50000\).
-
Subtask \(2\) (\(100\%\) số điểm): \(1 \le Q \le 150000\).
-
Trong mỗi test:
-
30% số test_case có \(1 \le n,k \le 10^5\).
-
100% số test_case có \(1 \le n,k \le 10^{18}\).
-
Example
Test 1
Input
1
1 1
Output
1
Note
Bài này đọc xong thấy có dễ ko mn :))
Phần giải thích cho mấy bạn chưa hiểu đề lắm:
Bình luận
\(P^k_n=\sum\limits_{i=1}^N[\sum\limits_{j=1}^k((-1)^{j+1}*C^j_k*i^{k-j})]\)
Ý anh Toilaaibanbietko7A4 là thế này hả?
.
cuối cùng cũng ac 😇😇😇😇
phần module thì mod từng hạng tử thôi
|| hint
sau 2 năm, tui cũng đã tìm ra công thức của bài này, sau đây mình sẽ chia sẽ công thức với mọi người mặc dù mình chưa ac(mình yếu phần modulo quá í mà :D). công thức của bài này là n ^ k (n mũ k). mình tìm được công thức này nhờ vào nhị thức niu-tơn, mọi người có thể tham khảo nhị thức niu-tơn tại đây https://toanthaydinh.com/nhi-thuc-newton/. chúc mọi người ac cho Toilaaibanbietko7A4 vui nha :D.
||
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
quá cen nha :>>
:>>
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Đọc xong muốn đập máy, mối q phải ít nhất là O(1) hoặc O(log n) gì gì đó mới ac