c++ - 具有 k 个断开顶点的三元组的总和

Question

考虑这些组件的大小是 a1, a2, a3,.... , ak。所以我们必须从给定的 k 个断开的组件中选择三个顶点，这可以通过多种方式完成。

S = 0;

for(i=1 ; i<= k ; i++)

    for(j=i+1 ; j<= k; j++)

        for(t=j+1 ; t<= k ; t++)

                S += a[i]*a[j]*a[t];
return S%(10^9+7)

所以你必须在 O(N) 时间内计算 S 的值。这可以通过一些观察来计算。

B[n-1] = count1[n];

    for(i=n-2;i>=0;i--)
 B[i] = (B[i+1] + count1[i+1])%MOD;

    for(i=1;i<n-1;i++)
 C[i] = (count1[i+1]*B[i+1])%MOD;


    D[n-2] = C[n-2];

    for(i=n-3;i>=1;i--)
 D[i] = (D[i+1] + C[i])%MOD;


    for(i=0;i<n-2;i++) 
sum = (sum + count1[i+1]*D[i+1])%MOD;

在这里使用 O(n) 没有找到三元组。我没有得到逻辑任何人都可以在这里解释 O(n) 方法。供参考 http://gauamgraph.blogspot.com/2015/09/kundu-and-tree.html?m=1

标签： c++triplet