Cần trợ giúp trong câu hỏi 1000000007 mod

Question

Tôi yếu về toán học và luôn gặp khó khăn với các vấn đề yêu cầu trả lời modulo một số số nguyên tố không.

ví dụ: (! 500/20) mod 1000000007

Tôi quen thuộc với BigIntegers nhưng tính modulo sau khi tính toán thừa của 500 (ngay cả sau khi sử dụng DP) dường như để có một tải trọng của thời gian.

Tôi muốn biết liệu có cách tiếp cận/đối phó cụ thể với các loại vấn đề này không.

Dưới đây là một vấn đề như vậy mà tôi đang cố gắng để giải quyết vào lúc này: http://www.codechef.com/FEB12/problems/WCOUNT

Nó sẽ thực sự hữu ích nếu ai đó có thể trực tiếp tôi để hướng dẫn hoặc một cách tiếp cận để xử lý những vấn đề mã hóa. Tôi quen thuộc với Java và C++.

Answer 1

Chìa khóa cho các tác vụ mô-đun số lớn này không tính toán kết quả đầy đủ trước khi thực hiện mô đun. Bạn nên giảm bớt các module trong các bước trung gian để giữ số lượng nhỏ:

500!/20! = 21 * 22 * 23 * ... * 500 

21 * 22 * 23 * 24 * 25 * 26 * 27 = 4475671200 

4475671200 mod 1000000007 = 475671172 
475671172 * 28 mod 1000000007 = 318792725 
318792725 * 29 mod 1000000007 = 244988962 
244988962 * 30 mod 1000000007 = 349668811 

... 

31768431 * 500 mod 1000000007 = 884215395 

500!/20! mod 1000000007 = 884215395 

Bạn không cần phải giảm mô đun ở mọi bước duy nhất. Chỉ cần làm điều đó thường xuyên đủ để giữ cho số lượng quá lớn.

---

Lưu ý rằng giá trị tối đa của long là 2^63 - 1. Vì vậy, thực hiện phép nhân 64 bit giữa hai giá trị số nguyên dương (ví dụ: một trong những toán hạng là một long) sẽ không tràn long. Bạn có thể thực hiện một cách an toàn hoạt động còn lại % sau đó (nếu điều đó là tích cực) và quay trở lại một số nguyên khi được yêu cầu.

Answer 2

Bắt đầu bằng cách quan sát 500!/20! là sản phẩm của tất cả các số từ 21 đến 500, bao gồm và Tiếp theo, quan sát bạn có thể thực hiện phép nhân modulo theo mục, lấy %1000000007 ở cuối mỗi thao tác. Bạn sẽ có thể viết chương trình của bạn ngay bây giờ. Hãy cẩn thận không để tràn số: 32 bit có thể không đủ.

Answer 3

Tôi nghĩ rằng đây có thể là của một số sử dụng cho bạn

for(mod=prime,res=1,i=20;i<501;i++) 
{ 
res*=i; // an obvious step to be done 
if(res>mod) // check if the number exceeds mod 
res%=mod; // so as to avoid the modulo as it is costly operation 
}