我们把 $n$ 个箱子的球摆开排在一起，每次就是等概率随机选一个球，然后在它后面加一个球，和它在同一个箱子。容易发现，$d$ 次操作之后，所有 ${n-1+d\choose n-1}$ 种可能的情况是等概率的。所以我们可以当作一个计数问题来做，也就是求 $x_i\ge 1,\sum x_i=n+d$ 的序列的前 $k$ 大之和。

第 $k$ 大的数等于 $\sum_{t\ge 1}[至少 k 个数大于等于 t]$。我们先来算有多少个序列恰好 $k$ 个数大于等于 $t$。二项式容斥，变为钦定 $k$ 个数大于等于 $t$，那么也就是 $f(k,t)={n-1+d-k(t-1)\choose n-1}$。

答案就应该是 $$ \sum_{i=1}^r\sum_{k=i}^n \sum_{j=k}^n \sum_{t\ge 1}(-1)^{j-k}{j\choose k}f(j,t){n\choose j} $$ 令 $g(k)={n\choose k}\sum_{t\ge 1} f(k,t)$，那么答案就是 $$ \sum_{i=1}^r\sum_{k=i}^n\sum_{j=k}^n (-1)^{j-k}{j\choose k}g(j) $$ 上式中枚举 $j$ 之后 $g(j)$ 的系数实际上就是一个简单的组合数，所以我们只需要求出 $g(j)$，然后就可以 $O(n)$ 求答案。

求 $g(j)$ 暴力是调和级数的 $O(d\log d)$，但实际上只需要对 $h(j)={n-1+d-j\choose n-1}$ 做一个狄利克雷后缀和，因此可以做到 $O(d\log\log d)$。

总时间复杂度 $O(n+d\log\log d)$。