#P17682. [Math+Girl×1] dancing With Myself in the sunset / Wheels Mst
[Math+Girl×1] dancing With Myself in the sunset / Wheels Mst
当前没有测试数据。
P17618
2s 2G
题目描述
给定 ,定义轮图 是无向图,点集 ,其中 依次连成环, 和其余每个点连边,共 条边。
对于 $\left[3,\left\lfloor\dfrac n2\right\rfloor+1\right]$ 中的每个 ,求在 上加边 后得到的新图中,所有 种给边赋上 的不同整数边权的方案中,最小生成树的权值和之和 。
输入格式
一行一个正整数 。
输出格式
一行 个整数,第 个数表示 时的答案,对 取模。
输入输出样例 #1
输入 #1
4
输出 #1
3857760
输入输出样例 #2
输入 #2
8
输出 #2
274314254 900658981 141086820
输入输出样例 #3
输入 #3
12
输出 #3
844621131 708548915 317841275 124930753 731097448
输入输出样例 #4
输入 #4
18
输出 #4
744963935 210055227 439652156 868477371 389817015 690785547 276112964 215894660
说明/提示
数据范围与约定
本题采用捆绑测试。
::cute-table{tuack}
| 子任务 | 分值 | |
|---|---|---|
对于所有数据,。
请注意常数因子对运行效率的影响。