I. Việc mở đầu

Bài toán phân tách kẹo Euler là một trong những bài toán tổ hợp xuất hiện từ thời xa xưa, đây là một bài bác toán rất hấp dẫn và có không ít ứng dụng vào Toán học. Khởi nguồn từ một sự việc rất đơn giản, nhà chưng học Leohard Euler sẽ phát biểu nó thành một câu hỏi như sau:

"Có mmm mẫu kẹo tương đương nhau, đề xuất chia chúng mang đến nnn em bé. Hỏi gồm bao nhiêu biện pháp chia kẹo như vậy?"

Bài toán tưởng chừ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ừ vấn đề này, người ta đã trở nên tân tiến ra phương pháp giải cho vô số vấn đề đếm khác nhau. Trong bài viết này, tôi sẽ giới thiệu tới chúng ta phương pháp giải việc chia kẹo Euler và một trong những ứng dụng từ cơ bạn dạng tới nâng cao của nó. Vớ nhiên, nội dung các bài toán sẽ liên quan nhiều cho tới lập trình, cho nên tôi sẽ làm lơ những vấn đề quá khó khăn (mà chỉ dành riêng cho học sinh siêng Toán).

Bạn đang xem: Bài toán chia kẹo và ứng dụng giải bài toán thanh gỗ

1. Phương thức giải câu hỏi cơ bản

Nếu call số kẹo mà mỗi em nhỏ bé nhận được lần lượ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 lúc ấ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 tuy nhiên ánh, coi rằng giữa mỗi em bé xíu có một số 000 cùng số kẹo của em nhỏ xíu thứ iii nhận thấy sẽ trình diễn bằng một dãy có xix_ixi​ số 1,1,1, thì bài toán trở thành đếm số thông số kỹ thuật có dạng:

*

Với mmm số 111 cùng n−1n - 1n−1 số 000

Như vậy, thực tế ta đã đếm số biện pháp đặt n−1n - 1n−1 số 000 vào một dãy tất 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ổ 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 xích toán. Giả dụ như việc yêu cầu đưa ra tác dụng là phần dư sau khoản thời gian chia cho 1 giá trị nào đó thì cần sử dụng các phương pháp phù phù hợp như Nghịch đảo modulo, Thuật toán bình phương và nhân tuyệt Phép nhân Ấn Độ tương ứng. Lập trình ở vị trí này không khó 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 dòng kẹo?

Bài toán rất có thể lắt léo rộng một chút, ví như như đề bài yêu cầu rằng khi phân chia kẹo, từng em nhỏ bé đều phải được trao ít độc nhất 111 chiếc kẹo. Lúc đó, 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 vấn đề 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. Lúc ấ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ì bài toán lại biến hóa dạng tương đương với câu hỏi cơ bản, bây giờ số nghiệm của phương trình đó là số cỗ giá trị (y1,y2,…,yn)(y_1, y_2, dots, y_n)(y1​,y2​,…,yn​) vừa lòng phương trình (1),(1),(1), đó 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 việc có dạng như hai bài toán nói bên trên đều hoàn toàn có thể phát biểu thành dạng tổng 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ương tự với việc 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ới s=∑i=1nais = sum_i = 1^n a_is=∑i=1n​ai​. Phương trình đã mang đến 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 nên xét tới cha trường vừa lòng kết quả:

Nếu ms,m ms, thì phương trình đã cho sẽ vô nghiệm.Nếu m=s,m = s,m=s, thì phương trình đang cho bao gồm 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ố bộ giá trị (y1,y2,…,yn)(y_1, y_2, dots, y_n)(y1​,y2​,…,yn​) vừa lòng 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 bác toán vận dụng của bí quyết chia kẹo Euler trong lập trình sẵn thi đấu, để nắm rõ hơn về vận dụng của cách làm này trong các kì thi lập trình!

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

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

Đề bài

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

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

Input:

Một dòng 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 mang đế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 vừa lòng gồm m+nm + nm+n bước đi (mỗi cách đi là một trong cạnh ô vuông). Tại từng bước đi chỉ được lựa chọn một trong hai giá bán trị tăng trưởng (ta đặt là 111) hoặc di chuyển sang cần (ta để là 000). Số bước tiến lên đúng bằng nnn với số bước sang bắt buộc đúng bởi mmm. Bài xích toán hôm nay dẫn đến việc tìm xem có bao nhiêu hàng nhị phân tất cả độ lâ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 câu hỏi chia kẹo Euler, công dụng cần tìm hôm nay 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 rượu cồn dựa trên tính chất 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 đo lường và tính toán modulo liên tục để tránh gây nên tràn số giả dụ như sử dụng ngôn từ C++.

Cài đặt

#include using namespace std;const int mod = 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 ni Tí vừa học hoàn thành về danh sách link trên trường. Cậu ấy đã có được học về cách hợp duy nhất hai danh sách liên kết. Khi ta hợp độc nhất vô nhị hai danh sách liên kết, lắp thêm tự của các thành phần của mỗi list không cố kỉnh đổi. Ví dụ, nếu 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 đ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 nhiên <1,4,3,2,5,6><1,4,3,2,5,6><1,4,3,2,5,6> không phù hợp lệ bởi vì 333 lép vế 222.

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

Input:

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

Tổng số cách để 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 chọn ra nnn địa điểm trong m+nm + nm+n vị trí để đặt nnn đồ vật thuộc các loại thứ 222 vào. Tác dụng không gồm gì đổi khác nếu như chúng ta chọn nó bởi (n+mm)n + m choose m(mn+m​).

Xem thêm:

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 tính chất sau (chính là tam giác Pascal, nếu các bạn chưa lưu giữ về bí quyết này thì hãy tìm hiểu lại bên 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ạo trước mảng nhì chiều giữ tam giác Pascal rồi gửi ra tác dụng của mỗi chạy thử case vào 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