P3790 文艺数学题

    • 36通过
    • 167提交
  • 题目提供者 will7101 管理员
  • 评测方式 云端评测
  • 标签 剪枝 枚举,暴力 生成树 洛谷原创 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    小Y在AK曼哈顿OI,CTSC和APIO之后,开始研究数学题。

    题目描述

    小Y有一张N个点,M条边的无向图(可能有重边、自环),每条边都有一个权值w。

    你需要计算:所有生成树的边权的最大公约数之和,具体操作见样例。

    生成树的定义:原图的一个连通子图,恰好有N-1条边。

    由于答案可能很大,需要对1000000007取模

    输入输出格式

    输入格式:

    第一行两个正整数N,M,表示点数和边数。

    接下来M行,每行三个正整数u,v,w,表示一条边连接u和v,权值为w。

    输出格式:

    输出一行一个数,表示答案对1000000007取模的值。

    输入输出样例

    输入样例#1: 复制
    4 5  
    1 2 12  
    1 3 9  
    2 4 6  
    3 4 8  
    1 4 4  
    输出样例#1: 复制
    15

    说明

    样例1的解释

    显然,这张图有8个不同的生成树。

    用 $(x,y,z)$ 表示x,y,z的最大公约数,则答案

    $=(12,6,8)+(6,8,9)+(8,9,12)+(9,12,6)+(9,4,6)+(12,4,8)+(12,4,9)+(6,4,8)$

    $=2+1+1+3+1+4+1+2$

    $=15$

    数据范围

    对于20%的数据, $N\le 10, M\le 20$ ;

    对于另外10%的数据, $N\le 12, M\le 24$ ;

    对于另外20%的数据, $N\le 60, M\le 3000$ ,且满足 $u_i+1=v_i$ ;

    对于另外20%的数据, $N\le 40, M\le 1000, W\le 1000$ ;

    对于另外15%的数据, $N\le 50, M\le 2000$ ;

    对于所有100%的数据, $N\le 60, M\le 3000, W\le 1000000$ ;

    标程展开

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。