Dice Dice Dice

Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

There are 1111 ways in which five 6-sided dice (sides numbered 1 to 6) can be rolled so that the top three numbers sum to 15. Some examples are: 
D1,D2,D3,D4,D5 = 4,3,6,3,5 
D1,D2,D3,D4,D5 = 4,3,3,5,6 
D1,D2,D3,D4,D5 = 3,3,3,6,6 
D1,D2,D3,D4,D5 = 6,6,3,3,3 
Now we have a extended problem:
In how many ways can n m-sided dice (sides numbered 1 to m) be rolled so that the top k numbers sum to p?

Input

There are multiple test cases. (about 15 groups)
For each test case, there is only four integers n, m, k, p (1 ≤ k ≤ n ≤ 20, 3 ≤ m ≤ 12)

Output

For each test case, output an integer indicating the answer.

Sample Input

5 6 3 15
6 6 3 15

Sample Output

1111
7770

Source

dut200901102

Manager

Information
Solved Number10
Submit Number14
Problem Tags
dfs and similar
dp
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel