这个概率怎么算？

用组合公式递归加剪枝？好像复杂度太高了。。。

动态规划不知道行不行 思路： 反过来算，算不存在差值为d的编号的概率。dp中每个子问题用剩余可选编号集合(rest)和剩余需要选取的标号个数(cnt)来表示，那么求解dp[rest][cnt]时，只需要遍历rest(设编号为x), 如果x仍然可选(判断选择x后是否会出现差值为d的编号对)，就加上这种情况，然后回溯判断下一个．．．．．． 这样的话，结果就等于1-dp[1~n][k] dp我也不是很熟，以上仅供参考～

并不是最多选一个吧。 相邻两段选一个。 然后优化到g 【 在 lanvent 的大作中提到: 】 : 并不知道数据范围，故贸然提思路 : 个人思路： : 反过来算，构造模d剩余系,假设n=a*d+b (b<d), 则可以分成 b组a+1个球 和 (d-b)组 a个球. : ...................

同个剩余系里面……差不止是d，还有2d(比如同时选1，1+2d也是合法啊）？ 【 在 lanvent 的大作中提到: 】 : 因为是求反，所以在每个剩余系中不能取1个以上的球。 : 最后求反的方案数是 : ans=C(n,k)-sum( C(b,i)*(a+1)^i*C(d-b,k-i)*a^(k-i) )(0<=i<=min(b,k),0<=k-i<=d-b ) : ...................

【 在 Macaulish64 的大作中提到: 】 : 同个剩余系里面……差不止是d，还有2d(比如同时选1，1+2d也是合法啊）？ 哦哦，对，理所当然在模意义下做了。

话说直接手算可以吗？～ 【 在 ztinpn (ztinpn) 的大作中提到: 】 : N个球编号1..N，随机抽k个球，求其中存在编号之差为给定值d的概率。 通过『我邮2.0』发布

你牛 【 在 hx0502001 的大作中提到: 】 : 话说直接手算可以吗？～ : : 【 在 ztinpn (ztinpn) 的大作中提到: 】 : : N个球编号1..N，随机抽k个球，求其中存在编号之差为给定值d的概率。 : : : [url : .........

猜一个大致思路 f[i][j] 为 选第i个球，并且i以后不选，选总共j个球的方案数 f[i][j] = sum{f[i-k][j-1] - f[i-d][j-2]}(0<k<d) + sum{f[i-k][j-1]}(d<k<=i) f[0][0] = 1 f[i][j] = 0 (j<0 | i<0) 最终概率 ans = sum{f[i][K]}(K<=i<=N) / C(N,K)

【 在 Thomas0726 的大作中提到: 】 : 猜一个大致思路 : f[i][j] 为 选第i个球，并且i以后不选，选总共j个球的方案数 : f[i][j] = sum{f[i-k][j-1] - f[i-d][j-2]}(0<k<d) + sum{f[i-k][j-1]}(d<k<=i) : ................... f[i-k][j-1]中的非法（存在差值为d）的方案不一定是f[i-d][j-2]转移来的，也可能是f[i-t][j-2](k<t<d)转移而来，只要该方案存在i-d这颗球。 简单想了下应该就是模d分组，每组选若干个不相邻的球，方案数相乘。