BZOJ 1430 小猴打架

题目大意

求N个点的最小生成树的排列个数。


根据一个经典公式和证明,一个完全图有$n^{n-2}$棵生成树。每棵生成树都有$(n-1)!$的排列,所以最终答案就是$n^{n-2} \times (n-1)!$

#include <cstdio>
#define MO 9999991
long long n,ans=1;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n-2;++i) ans=(ans*n)%MO;
    for(int i=1;i<=n-1;++i) ans=(ans*i)%MO;
    printf("%lld\n",ans);
    return 0;
}

BZOJ 2631 tree

题目大意

维护一颗树,支持:

  1. $u \to v$的路径上的点的权值加上自然数c
  2. 删除边$u_1 \to v_1$,加入边$u_2 \to v_2$
  3. $u \to v$的路径上的点的权值乘上自然数c
  4. 询问路径$u \to v$上的点的权值和

阅读剩余部分 -

Codeforces 892 D Gluttony

题目大意

你有一个包含$n$个元素的序列$a$(其中元素不重).请构建一个$a$的排列序列$b$使得对于任意非空子集$S = \{ x_1,x_2,...,x_k \} (1 \le x_i \le n, 0 \lt k \lt n)$都保证

$$\sum_{i=1}^{k} a_{x_i} \neq \sum_{i=1}^{k} b_{x_i}$$

阅读剩余部分 -

最新文章

最近回复

板块

杂项

    本站托管于学园都市
    由御坂网络提供CDN加速服务