设置桩柱

Question

如果你想建立一个栅栏，并有不同的长度板可用，有许多不同的方式来设置你的职位。因此，给定一个最小和最大的板长，一些板，以及总长度，计算出你能安排它们的方式有多少种。

输入

输入是四个正整数：

• 敏:可用的最小的板。将是>0。
• 最大的董事会。将是>min。
• 计数:要使用的板数。将是>0。
• 长度:围栏的总长度。对于有效的围栏，这应该是>=min*count和<=max*count

单板可以是min和max之间的任意整数长度(包括在内)。

输出

输出一个数字，表示您可以排列栅栏的方式的数量。

示例

对于输入(按上面列出的顺序排列) 2 3 4 10，您可以通过六种方式排列板：

2233
2323
2332
3223
3232
3322

所以输出是6。如果您的输入是1 3 4 6，则输出是10，因为有十种方法可以这样做：

1113   1212
1131   1221
1311   2112
3111   2121
1122   2211

Input          Output
5 10 6 45      4332
1 100 6 302    1204782674
27 53 8 315    4899086560
1 10 11 70     2570003777 
1 6 15 47      20114111295
4 8 150 600    1              // all boards length 4
1 10 100 80    0              // invalid, you can't put 100 boards in 80 length

当然，有一种天真的方法可以做到这一点：

long f(int min, int max, int count, int length){
    if(count==1)
        return 1;
    long num = 0;
    for(int i=min;i<=max;i++){
        int goal = length - i;
        if(goal <= max*(count-1) && goal >= min*(count-1)){
            num += f(min,max,count-1,goal);
        }
    }
    return num;
}

规则

上面给出的算法对于小的输入可以很好的工作，但是它很容易使long溢出到更大的输入。即使是任意长度的数字，它也是极其低效的。我相信是O((max-min+1)^count)。

要想在这个问题上被认为是有效的，您应该能够在我的1 10 100 700上计算一个小时之内的输入i7。如果有一个比上面的算法更有效的算法，这不应该是一个问题。我将测试任何我认为可能接近极限的条目。如果您的算法运行时间超过几分钟，您应该使用一种免费的语言(在linux上)来方便测试。

代码可以采用完整的程序或函数的形式，输入/输出作为任何一个标准方法。以字节为单位的最短代码获胜。

Answer 1

Dyalog Unicode，55 字节数

⎕CY'dfns'
{0::0⋄⍺⊃⍵{+big⌿↑(⍳1+¯1⊥⍺)⌽¨⊂0,⍣(⊢/⍺)⊢⍵}⍣⍺⍺⊢1}

在网上试试！(没有大，那么快，但不准确)

该算法的时间复杂度为O(m(m-n)c^2)，其中m和n为max和min，c为计数，忽略了bigint加法的成本(这不是内置的语言，因此效率极低)。它并不是最快的，但它仍然比蛮力快得多，因为它在3分钟内在我的电脑上为1 10 100 700返回正确的结果。

若要使用，请将内联运算符分配给f，并以length (count f) min max的形式调用它。

⎕CY'dfns'  ⍝ Load dfns library, so we can use `+big`

{0::0⋄...}  ⍝ If any error occurs, return 0
⍺⊃⍵{...}⍣⍺⍺⊢1  ⍝ Build the vector of all possible combinations by
               ⍝ taking the polynomial represented by ⍵ raised to the power of ⍺⍺,
               ⍝ then fetch the ⍺-th coefficient (might error if ⍺ is out of range)
0,⍣(⊢/⍺)⊢⍵    ⍝ Prepend "max" copies of 0s to the current polynomial
(⍳1+¯1⊥⍺)⌽¨⊂  ⍝ Generate the list of ^ rotated 0..(max-min) times
+big⌿↑        ⍝ Promote to matrix and sum the numbers vertically