Arranging Fenceposts

Ruby: 106 98 93 bytes

Update: Changed cache key type from strings to arrays. (-5)

Update: Storing the initial condition in the cache payed out quite well. (-8) However, it increases the runtime for the test case to roughly 2 seconds.

I simply use memoization. I guess it can be further golfed as my Ruby skills are far from perfect.

@m={[0,0]=>1}
def f(l,u,c,s)
  @m[[c,s]]||=s<0?0:(l..u).map{|x|f(l,u,c-1,s-x)}.reduce(:+)
end

Note that it runs for only one test case at a time, since I don't cache the min and max values (l and u, respectively). Here is my output for 1 10 100 700:

121130639107583774681451741625922964085713989291260198434849317132762403014516376282321342995

real    0m0.316s
user    0m0.312s
sys     0m0.004s

APL (Dyalog Unicode), 55 bytes

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

Try it online! (without big, so fast but inaccurate)

The time complexity of the algorithm is \$O(m(m-n)c^2)\$, where \$m\$ and \$n\$ are max and min, and \$c\$ is the count, ignoring the cost of bigint addition (which is not a language built-in, and therefore horribly inefficient). It is nowhere close to the fastest, but it's still much faster than brute-force, as it returns the correct result for 1 10 100 700 in 3 minutes on my PC.

To use, assign the inline operator to f and call it in the form of 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