BÀI TOÁN CHIA KẸO EULER

     
I. Bài toán mở đầu

Bài toán phân tách 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 hay và có nhiều ứng dụng vào Toán học. Bắt đầu từ một sự việc rất đối chọi giản, nhà bác bỏ học Leohard Euler đã phát biểu nó thành một việc như sau:

"Có mmm chiếc kẹo giống nhau, nên chia chúng mang lại nnn em bé. Hỏi gồm bao nhiêu giải pháp chia kẹo như vậy?"

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

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

1. Phương pháp giải bài toán cơ bản

Nếu hotline số kẹo mà lại mỗi em bé nhỏ 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 bác toán lúc ấy sẽ trở thành: Đếm số nghiệm nguyên ko â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ỏ bé có một số trong những 000 cùng số kẹo của em bé 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ì bài toán 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ố biện pháp đặt n−1n - 1n−1 số 000 vào một trong những dãy có m+n−1m + n - 1m+n−1 vị trí, còn sót lại sẽ là các số 111. Theo quy tắc tổ hợp không lặp, số nghiệm của việc 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 để ý cả cho tới giới hạn tài liệu của bài bác toán. Nếu như như việc yêu mong đưa ra hiệu quả là phần dư sau khi chia cho một giá trị làm sao đó thì nên cần sử dụng các phương thức phù đúng theo như Nghịch đảo modulo, Thuật toán bình phương cùng nhân tốt Phép nhân Ấn Độ tương ứng. Lập trình ở phần này ko khó nên tôi sẽ không viết lại code nữa!

2. Nếu các em bé đều đề nghị nhận được ít nhất 1 mẫu kẹo?

Bài toán rất có thể lắt léo hơn một chút, nếu như đề bài xích yêu ước rằng khi phân tách kẹo, mỗi em nhỏ xíu đều phải được trao ít độc nhất vô nhị 111 loại kẹo. Khi đó, việc 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 vừa lòng kết quả:

Nếu mnm mn thì phương trình vô nghiệm.Nếu m≤nm le nm≤n thì việc lại biến chuyển dạng giống như với câu hỏi cơ bản, hôm nay 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), đó là:

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

3. Phát triển bài toán tổng quát

Các việc có dạng như hai vấn đề nói trên đều rất 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; 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ương tự với câu hỏi số 2, ta điện thoại tư vấn 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ới 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 buộc phải xét tới bố trường vừa lòng kết quả:

Nếu ms,m ms, thì phương trình đã đến sẽ vô nghiệm.Nếu m=s,m = s,m=s, thì phương trình đang cho tất cả 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 phải đếm số cỗ giá trị (y1,y2,…,yn)(y_1, y_2, dots, y_n)(y1​,y2​,…,yn​) thỏa mãn phương trình (2),(2),(2), đó là:

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

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

II. Một trong những bài toán minh họa

1. Đếm mặt đường đi

Đề bài

Cho một lưới gồm những ô vuông. Các ô được đánh số từ 000 đến mmm theo chiều từ trái sang buộc phải và từ bỏ 000 mang đến nnn theo hướng từ bên dưới lên trên. Mang sử ta vẫn ở ô (0,0);(0,0);(0,0); ta chỉ hoàn toàn có thể di gửi trên cạnh các ô vuông theo hướng từ trái sang đề nghị hoặc từ bên dưới lên trên.

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

Input:

Một chiếc duy nhất đựng hai số nguyên mmm và 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 tác dụng của bài toán sau khi chia cho 109+710^9 + 7109+7.

Sample Input:

2 3Sample Output:

10

Ý tưởng

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

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

Ta rất có thể tính tổng hợp (nk)n choose k(kn​) bởi quy hoạch động 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 phù hợp với việc giám sát và đo lường modulo liên tiếp để tránh tạo ra tràn số ví như như sử dụng ngôn từ C++.

Cài đặt

#include using namespace std;const int thủ thuật = 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 nhất danh sách

Đề bài

Hôm nay Tí vừa học hoàn thành về danh sách link trên trường. Cậu ấy đã có học về cách hợp nhất hai danh sách liên kết. Lúc ta hợp nhất hai danh sách liên kết, vật dụng tự của các bộ phận của mỗi danh sách không nắm đổi. Ví dụ, trường hợp ta hợp duy nhất <1,2,3><1,2,3><1,2,3> và <4,5,6><4,5,6><4,5,6>, ta vẫn 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 nhiên <1,4,3,2,5,6><1,4,3,2,5,6><1,4,3,2,5,6> chưa hợp lệ vì 333 thua cuộc 222.

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

Xem thêm: Lời Bài Hát Lí Cây Đa & Bài Đọc Thêm Hội Lim, Lời Bài Hát Lí Cây Đa

Input:

Dòng trước tiên chứa số nguyên ttt chỉ con số truy vấn.ttt chiếc tiếp theo, mỗi loại chứa một truy hỏi vấn bao gồm hai số nguyên là nnn và 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 đáp án của bài bác toán sau thời điểm chia đến 109+710^9 + 7109+7 cùng lấy số dư làm 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 để thích hợp nhất những 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 nên hợp nhất hai list gồm mmm với nnn phần tử lại với nhau. Điều này tương đương với việc bố trí mmm đồ vật thuộc cùng một nhiều loại với nnn vật cùng thuộc nhiều loại khác trên và một hàng. Đây chính là bài toán chia kẹo Euler!

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

Xem thêm: Top 15+ Giải Bt Lịch Sử 8 - Giải Vở Bài Tập Lịch Sử 8 Hay Nhất

Ta hoàn toàn có thể tính tổ hợp (nk)n choose k(kn​) bằng quy hoạch rượu cồn dựa trên đặc thù sau (chính là tam giác Pascal, nếu chúng ta chưa lưu giữ về phương pháp này thì nên tìm phát âm 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). Các bạn nên khởi chế tạo ra trước mảng nhì chiều giữ tam giác Pascal rồi đưa ra tác dụng của mỗi chạy thử case trong O(1)O(1)O(1).

Cài đặt

#include #define int long long using namespace std;const int mod = 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ài liệu tham khảo