参考说明：
added saltyfish/2016 ACM/ICPC Asia Regional Qingdao Onsite.page
Fibnacci
D 概率 cpp 1double qp(double a, int p){ 2 double ans = 1; 3 while(p){ 4 if(p & 1) ans *= a; 5 a *= a; p >>= 1; 6 } 7 return ans; 8} 9 10int n; 11int num[20]; 12double p[20], ans[20]; 13 14//除了x硬币其余硬币活不到第k轮的概率 15double sove(int x, int k){ 16 double ans = 1; 17 for(int i = 0; i < n; i++){ 18 if(i == x) continue; 19 ans *= qp((1 - qp(p[i], k)), num[i]); 20 } 21 return ans; 22} 23 24int main(){ 25// Fastin; 26 int t; scanf("%d", &t); while(t--){ 27 scanf("%d", &n); 28 fro(int i = 0; i < n; i++){ 29 scanf("%d %lf", num + i, p + i); 30 ans[i] = 0; 31 } 32 if(n == 1) printf("1.000000\n"); 33 else{ 34 //实验100轮 35 for(int i = 1; i <= 100; i++) for(int x = 0; x < n; x++){ 36 ans[x] += (sove(x, i) - sove(x, i - 1)) * (1 - qp((1 - qp(p[x], i)), num[x])); 37 } 38 for(int i = 0; i < n; i++){ 39 printf("%.6f", ans[i]); 40 if(i != n - 1) printf(" "); 41 else printf("\n"); 42 } 43 } 44 } 45 return 0; 46} 考虑所有三元组，图是若干个团之并的充要条件是不存在某个三元组中有两条边（实际上就是要满足传递性），于是任取一个有两条边的三元组，枚举加上剩下的边或者删除现有两条边之一，修改一条边之后会有$O(n)$个三元组受影响，暴力修改这些三元组，同时用一个队列+时间戳维护当前有两条边的三元组，搜$10$步即可，复杂度是$O(n^3+n3^{10})$