题目描述
您正在处理要为每个客户端分配唯一ID的特定系统的后端。但是，系统是分布式的，并且有许多组件，每个组件都必须能够为客户端分配ID。换句话说，您希望每个组件都使用尽可能少的组件之间的通信来分配ID。您已经确定保持系统分布比确保所有客户端都具有唯一ID更重要。因此，您正在考虑让每个组件从大量可能的ID中随机分配ID，并在每天结束时同步分配的ID。换句话说，每个组件将根据所有组件分配的ID在每天结束时更新其可用ID列表。
现在，有两种方法可以做到这一点。第一种方法是每个组件分配ID是随机的。换句话说，组件没有任何记忆，这可能多次分配相同的ID。第二种方法是让每个组件都记住它们分配了哪些ID，这样一个组件不会多次分配相同的ID。然而，两个不同的组件有可能分配相同的ID，但一个组件不会多次分配相同的ID。现在，事实证明第一个方法实现起来稍微便宜一些，但它会明显导致更多冲突（当多个客户端分配相同的ID时会发生冲突）。所以，您的任务是模拟两个系统，并计算出在两个方法中出现冲突的概率，然后返回两个概率的差的绝对值。
输入输出格式
输入格式
多组测试数据。
第一行，一个整数G，表示有G组测试数据。 1 <= G <= 10
每组测试数据格式：
第一行，两个整数，n 和 IDS。2 <= n <= 50， 1000<=IDS<=2^31。 n表示总共有n个组件。内存池里面总共有IDS个不同的ID可以喷配。
第二行，n个整数，第i个整数是第i个组件需要分配的ID的个数，记为c[i]。 0 <= c[i] <= 10000。
输出格式
共G行，共G行，每行一个实数，误差不超过0.0001。
输入输出样例
输入样例
10
2 1000
20 20
2 123456
123 456
13 2147483647
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
2 1000
1005 1005
43 2001034851
6159 4927 6323 2339 7797 9793 6654 5711 5326 3700 945 3340 738 5359 9794 5659 7476 8771 483 6621 2119 6778 7009 3695 7841 8748 9044 2376 5703 1783 4337 9436 9444 9440 57 5176 9658 1417 5417 3909 9897 7066 6760
34 648336135
6764 5605 9981 4914 4178 2166 912 8102 5494 926 1552 949 3981 4245 8396 8824 3966 3639 3711 3231 88 1066 2450 3738 4262 2092 3019 1168 7292 4754 3344 795 2733 8359
6 93207251
4705 2595 9038 1057 7607 3653
9 712190492
4178 3432 9946 5782 9952 936 6373 5366 8409
41 26492068
6043 1635 3514 4539 2272 8789 1237 6489 6766 7007 7661 5122 8803 1132 897 6942 5311 5406 1674 2633 9271 9826 7702 4326 8044 2663 7139 4309 595 1216 7553 5929 6752 4217 6811 8280 8971 4482 1262 1441 5804
43 1478022888
5251 7545 1155 362 9600 5280 184 2520 9142 1859 5457 146 8297 7220 7012 6654 1476 8232 6899 4175 9404 4678 7090 5530 9643 901 9413 5136 2853 5392 4013 6522 6788 5164 1245 7458 8758 9494 7120 776 4243 2098 7273
输出样例
0.2113618990410422
0.3769052883184334
0.0069090268185510555
0.0
1.6742947149701077E-7
4.5319887938925983E-7
0.02036272439195439
0.040864223266969896
1.0E-323
1.3172076603021851E-8
题解
这里定义$sum=sum_{i=1}^{n}a[i]$。
易得概率差为$abs((1 - frac{ prod_{i=1}^{sum}ids-i+1 }{ids^{sum}}) - (1 - frac{ prod_{i=1}^{sum}ids-i+1 }{ prod_{i=1}^{n} frac{ids!}{(ids-a[i])!}}))$。
这个不是很好算，我们再整理得$abs( prod_{i=1}^{sum}frac{ids-i+1}{ids} - frac{ prod_{i=1}^{sum}ids-i+1 }{ prod_{i=1}^{n} prod_{j=1}^{a[i]} ids-j+1})$。
可以看到$O(sum)$的暴力即可过。
#include <iostream> #include <fstream> #include <cstdio> #define MAX_N (50 + 5) #define abs(x) ((x) >= 0 ? (x) : -(x)) using namespace std; int G; int n; unsigned ids, sum; int a[MAX_N]; int main() { // freopen("2797.in", "r", stdin); // freopen("2797.out", "w", stdout); scanf("%d", &G); double p1, p2; int cnt; while(G--) { scanf("%d%u", &n, &ids); sum = 0; for(register int i = 1; i <= n; ++i) { scanf("%d", a + i); sum += a[i]; } if(sum > ids) { printf("%lf ", 0.0); // 写0会wa，必须写浮点型 continue; } p1 = p2 = 1; cnt = 0; for(register int i = 1; i <= sum; ++i) { p1 *= (double)(ids - i + 1) / ids; } for(register int i = 1; i <= n; ++i) { for(register int j = 1; j <= a[i]; ++j) { p2 *= (double)(ids - cnt++) / (ids - j + 1); } } printf("%lf ", abs(p1 - p2)); } return 0; }