Bài toán chia kẹo của euler

     
I. Câu hỏi mở đầu

Bài toán chia kẹo Euler là 1 trong những bài toán tổ hợp mở ra từ thời xa xưa, đấy là một bài bác toán rất lôi cuốn và có tương đối nhiều ứng dụng vào Toán học. Khởi nguồn từ một vấn đề rất solo giản, nhà bác học Leohard Euler đã phát biểu nó thành một câu hỏi như sau:

"Có mmm dòng kẹo tương đương nhau, đề xuất chia chúng mang lại nnn em bé. Hỏi tất cả bao nhiêu bí quyết chia kẹo như vậy?"

Bài toán tưởng chừng như đơn giản, nhưng nó lại gây khó khăn cho ít nhiều học sinh. Từ bài toán này, người ta đã cải cách và phát triển ra bí quyết giải mang lại vô số việc đếm khác nhau. Trong nội dung bài viết này, tôi sẽ giới thiệu tới các bạn phương pháp giải câu hỏi chia kẹo Euler và một số ứng dụng tự cơ phiên bản tới nâng cao của nó. Tất nhiên, nội dung các bài toán sẽ liên quan nhiều tới lập trình, vì thế tôi sẽ bỏ qua mất những bài toán quá cực nhọc (mà chỉ giành riêng cho học sinh siêng Toán).

Bạn đang xem: Bài toán chia kẹo của euler

1. Phương pháp giải việc cơ bản

Nếu gọi số kẹo mà mỗi em bé nhận được theo thứ tự là x1,x2,…,xn (0≤xi≤m;∀i:1≤i≤n)x_1, x_2, dots, x_n (0 le x_i le m; forall i: 1 le i le n)x1​,x2​,…,xn​ (0≤xi​≤m;∀i:1≤i≤n). Bài toán khi ấy sẽ trở thành: Đếm số nghiệm nguyên không âm của phương trình:

x1+x2+⋯+xn=mx_1 + x_2 + cdots + x_n = mx1​+x2​+⋯+xn​=m

Sử dụng kĩ thuật song ánh, coi rằng giữa mỗi em nhỏ xíu có một trong những 000 với số kẹo của em nhỏ xíu thứ iii nhận thấy sẽ màn biểu diễn bằng một dãy tất cả xix_ixi​ số 1,1,1, thì câu hỏi trở thành đếm số cấu hình có dạng:

*

Với mmm số 111 và n−1n - 1n−1 số 000

Như vậy, thực tiễn ta đã đếm số giải pháp đặt n−1n - 1n−1 số 000 vào một dãy có m+n−1m + n - 1m+n−1 vị trí, còn sót lại sẽ là những số 111. Theo quy tắc tổng hợp không lặp, số nghiệm của bài toán sẽ là:

Cm+n−1n−1C^n - 1_m + n - 1Cm+n−1n−1​

Tuy nhiên, lúc lập trình các các bạn sẽ cần xem xét cả cho tới giới hạn dữ liệu của bài toán. Ví như như vấn đề yêu ước đưa ra công dụng là phần dư sau thời điểm chia cho một giá trị như thế nào đó thì nên cần sử dụng các phương pháp phù phù hợp như Nghịch hòn đảo modulo, Thuật toán bình phương cùng nhân giỏi Phép nhân Ấn Độ tương ứng. Lập trình tại phần này ko khó buộc phải tôi sẽ không viết lại code nữa!

2. Nếu các em bé bỏng đều buộc phải nhận được ít nhất 1 mẫu kẹo?

Bài toán có thể lắt léo rộng một chút, nếu như như đề bài xích yêu cầu rằng khi phân tách kẹo, từng em nhỏ nhắn đều phải được trao ít độc nhất 111 chiếc kẹo. Lúc đó, câu hỏi sẽ trở thành: Đếm số nghiệm nguyên dương của phương trình:

x1+x2+⋯+xn=mx_1 + x_2 + cdots + x_n = mx1​+x2​+⋯+xn​=m

Đối với việc này, ta giải như sau: Đặt yi=xi−1;∀i:1≤i≤ny_i = x_i - 1; forall i: 1 le i le nyi​=xi​−1;∀i:1≤i≤n. Khi ấy ta có:

y1+y2+⋯+yn=x1+x2+⋯+xn−n=m−n (1)y_1 + y_2 + cdots + y_n = x_1 + x_2 + cdots + x_n - n = m - n (1)y1​+y2​+⋯+yn​=x1​+x2​+⋯+xn​−n=m−n (1)

Lúc này phương trình xảy ra hai trường hòa hợp kết quả:

Nếu mnm mn thì phương trình vô nghiệm.Nếu m≤nm le nm≤n thì bài toán lại đổi mới dạng tương đương với việc cơ bản, từ bây giờ số nghiệm của phương trình chính là số bộ giá trị (y1,y2,…,yn)(y_1, y_2, dots, y_n)(y1​,y2​,…,yn​) thỏa mãn nhu cầu phương trình (1),(1),(1), kia là:

Cm−1n−1C^n - 1_m - 1Cm−1n−1​

3. Cải tiến và phát triển bài toán tổng quát

Các câu hỏi có dạng như hai vấn đề nói bên trên đều hoàn toàn có thể phát biểu thành dạng bao quát như sau: Đếm số nghiệm nguyên của phương trình x1+x2+⋯+xn=m;x_1 + x_2 + cdots + x_n = m;x1​+x2​+⋯+xn​=m; cùng với xi≥ai (∀i:1≤i≤n)x_i ge a_i (forall i: 1 le i le n)xi​≥ai​ (∀i:1≤i≤n).

Lời giải của vấn đề này tựa như với vấn đề số 2, ta hotline yi=xi−ai;∀i:1≤i≤ny_i = x_i - a_i; forall i: 1 le i le nyi​=xi​−ai​;∀i:1≤i≤n và s=∑i=1nais = sum_i = 1^n a_is=∑i=1n​ai​. Phương trình đã cho sẽ trở thành:

y1+y2+⋯+yn=(x1−a1)+(x2−a2)+⋯+(xn−an)=m−s (2)y_1 + y_2 + cdots + y_n = (x_1 - a_1) + (x_2 - a_2) + cdots + (x_n - a_n) = m - s (2)y1​+y2​+⋯+yn​=(x1​−a1​)+(x2​−a2​)+⋯+(xn​−an​)=m−s (2)

Giờ ta đề xuất xét tới tía trường thích hợp kết quả:

Nếu ms,m ms, thì phương trình đã mang đến sẽ vô nghiệm.Nếu m=s,m = s,m=s, thì phương trình vẫn cho tất cả duy duy nhất một nghiệm là xi=ai;∀i:1≤i≤nx_i = a_i; forall i: 1 le i le nxi​=ai​;∀i:1≤i≤n.Nếu m>s,m > s,m>s, thì ta cần đếm số cỗ giá trị (y1,y2,…,yn)(y_1, y_2, dots, y_n)(y1​,y2​,…,yn​) thỏa mãn nhu cầu phương trình (2),(2),(2), kia là:

Cm+n−s−1n−1C^n - 1_m + n - s - 1Cm+n−s−1n−1​

Bây giờ họ hãy thuộc xét một vài bài toán ứng dụng của công thức chia kẹo Euler trong xây dựng thi đấu, để làm rõ hơn về áp dụng của cách làm này trong số kì thi lập trình!

II. Một số bài toán minh họa

1. Đếm con đường đi

Đề bài

Cho một lưới gồm các ô vuông. Các ô được đặt số từ 000 cho mmm theo chiều từ trái sang buộc phải và từ bỏ 000 cho nnn theo chiều từ bên dưới lên trên. Trả sử ta sẽ ở ô (0,0);(0,0);(0,0); ta chỉ rất có thể di đưa trên cạnh các ô vuông theo chiều từ trái sang phải hoặc từ dưới lên trên.

Yêu cầu: Hãy tính số mặt đường đi khác nhau từ ô (0,0)(0,0)(0,0) mang lại ô (m,n)(m,n)(m,n) của lưới ô vuông?

Input:

Một chiếc duy nhất chứa hai số nguyên mmm cùng nnn.

Ràng buộc:

1≤m,n≤50001 le m, n le 50001≤m,n≤5000.m+n≤5000m + n le 5000m+n≤5000.

Output:

In ra số dư của kết quả của bài xích toán sau khoản thời gian chia đến 109+710^9 + 7109+7.

Sample Input:

2 3Sample Output:

10

Ý tưởng

Nhận xét thấy, một con đường đi thỏa mãn gồm m+nm + nm+n bước tiến (mỗi bước đi là một trong cạnh ô vuông). Tại mỗi bước đi chỉ được chọn 1 trong hai giá chỉ trị đi lên (ta để là 111) hoặc di chuyển sang buộc phải (ta đặt là 000). Số bước tiến lên đúng bằng nnn với số bước sang buộc phải đúng bởi mmm. Bài toán lúc này dẫn đến việc đào bới tìm kiếm xem bao gồm bao nhiêu dãy nhị phân có độ nhiều năm m+nm + nm+n trong các số đó có đúng nnn thành phần có mức giá trị bằng 111.

Dựa trên việc chia kẹo Euler, kết quả cần tìm lúc này là (m+nm)m + n choose m(mm+n​).

Ta rất có thể tính tổ hợp (nk)n choose k(kn​) bởi quy hoạch hễ dựa trên đặc thù sau của tổ hợp:

(nk)=(n−1k−1)+(n−1k)n choose k = n - 1 choose k - 1 + n - 1 choose k(kn​)=(k−1n−1​)+(kn−1​)

Độ phức tạp: O(n2)O(n^2)O(n2). Các bạn cần kết hợp với việc thống kê giám sát modulo liên tiếp để tránh gây nên tràn số trường hợp như sử dụng ngữ điệu C++.

Cài đặt

#include using namespace std;const int hack = 1e9 + 7;long long ncr<5005><5005>, n, m;void pre_compute() { int k; for (int i = 0; i > 1; for (int j = 1; j > m >> n; pre_compute(); cout

2. Hợp duy nhất danh sách

Đề bài

Hôm ni Tí vừa học ngừng về danh sách links trên trường. Cậu ấy đã được học về phong thái hợp duy nhất hai danh sách liên kết. Khi ta hợp tốt nhất hai danh sách liên kết, sản phẩm tự của các thành phần của mỗi list không cố đổi. Ví dụ, ví như ta hợp tuyệt nhất <1,2,3><1,2,3><1,2,3> và <4,5,6><4,5,6><4,5,6>, ta đang thu được danh sách mới là <1,4,2,3,5,6><1,4,2,3,5,6><1,4,2,3,5,6>, tuy vậy <1,4,3,2,5,6><1,4,3,2,5,6><1,4,3,2,5,6> không hợp lệ do 333 đứng sau 222.

Yêu cầu: Tí bao gồm hai danh sách link gồm nnn với mmm phần tử, hãy góp cậu ấy tính xem bao gồm bao nhiêu phương pháp để hợp độc nhất vô nhị cả nhị danh sách. Dữ liệu bảo vệ rằng n+mn + mn+m phần tử trong hai danh sách đều phân biệt.

Xem thêm: Vàng Có Khối Lượng Riêng Của Vàng Có Khối Lượng Riêng Là 1,93

Input:

Dòng thứ nhất chứa số nguyên ttt chỉ số lượng truy vấn.ttt chiếc tiếp theo, mỗi cái chứa một truy vấn vấn có hai số nguyên là nnn với mmm.

Ràng buộc:

1≤t≤101 le t le 101≤t≤10.1≤n,m≤1001 le n, m le 1001≤n,m≤100.

Output:

In ra câu trả lời của bài bác toán sau khoản thời gian chia đến 109+710^9 + 7109+7 và lấy số dư làm cho kết quả.

Sample Input:

12 2Sample Output:

6Giải thích:

Giả sử hai danh sách là <1,2><1,2><1,2> và <3,4><3,4><3,4>, các cách khác nhau để đúng theo nhất các danh sách này là:

<1,2,3,4><1,2,3,4><1,2,3,4>.<1,3,2,4><1,3,2,4><1,3,2,4>.<3,4,1,2><3,4,1,2><3,4,1,2>.<3,1,4,2><3,1,4,2><3,1,4,2>.<1,3,4,2><1,3,4,2><1,3,4,2>.<3,1,2,4><3,1,2,4><3,1,2,4>.

Ý tưởng

Bạn phải hợp độc nhất hai danh sách gồm mmm với nnn bộ phận lại cùng với nhau. Điều này tương đương với việc bố trí mmm thứ thuộc cùng một loại với nnn vật thuộc thuộc một số loại khác trên cùng một hàng. Đây đó là bài toán phân tách kẹo Euler!

Tổng số phương pháp để hợp nhất hai list sẽ là (n+mn)n + m choose n(nn+m​). Lí do là vì ta cần lựa chọn ra nnn địa chỉ trong m+nm + nm+n vị trí để tại vị nnn đồ thuộc loại thứ 222 vào. Tác dụng không gồm gì biến hóa nếu như các bạn chọn nó bởi (n+mm)n + m choose m(mn+m​).

Xem thêm: Top 11 Bài Phân Tích 8 Câu Cuối Trao Duyên, Phân Tích 8 Câu Cuối Đoạn Trích Trao Duyên

Ta hoàn toàn có thể tính tổ hợp (nk)n choose k(kn​) bởi quy hoạch đụng dựa trên tính chất sau (chính là tam giác Pascal, nếu các bạn chưa lưu giữ về công thức này thì nên tìm hiểu lại trên internet):

(nk)=(n−1k−1)+(n−1k)n choose k = n - 1 choose k - 1 + n - 1 choose k(kn​)=(k−1n−1​)+(kn−1​)

Độ phức tạp: O(n2)O(n^2)O(n2). Chúng ta nên khởi chế tác trước mảng hai chiều giữ tam giác Pascal rồi gửi ra công dụng của mỗi test case vào O(1)O(1)O(1).

Cài đặt

#include #define int long long using namespace std;const int hack = 1e9 + 7;void pre_compute(vector > &ncr, int max_size){ ncr = vector >(max_size + 1, vector (max_size + 1)); for (int i = 0; i > ncr; pre_compute(ncr, 200); int t; cin >> t; while (t--) { int n, m; cin >> n >> m; cout III. Tư liệu tham khảo