【bzoj 2467】[中山市选2010]生成树（数论--排列组合）

港控/mmm° 2021-12-17 07:21 150阅读 0赞

**题目：**有一种图形叫做五角形圈。一个五角形圈的中心有1个由n个顶点和n条边组成的圈。在中心的这个n边圈的每一条边同时也是某一个五角形的一条边，一共有n个不同的五角形。这些五角形只在五角形圈的中心的圈上有公共的顶点。现在给定一个n五角形圈，你的任务就是求出n五角形圈的不同生成树的数目。还记得什么是图的生成树吗？一个图的生成树是保留原图的所有顶点以及顶点的数目减去一这么多条边,从而生成的一棵树。注意：在给定的n五角形圈中所有顶点均视为不同的顶点。

**解法：**题目是问使这 N 五角形圈生成树的种数。而生成树就是要 N-1 条边，无环。我们的目标就是破环环，也就是各个封闭图形。  
首先，我们可以考虑中间的 N边形 一定要删一条边，C(n,1)。再是周围的 N 个五边形，有 N-1 个仍是五边形，各删一条边 C(5,1)^(n-1)，有一个只剩四条边，删一条边 C(4,1)。综合起来就是 C(n,1)\*C(5,1)^(n-1)\*C(4,1) 。

1 #include<cstdio>
     2 #include<cstdlib>
     3 #include<cstring>
     4 using namespace std;
     5 #define N 110
     6 #define mod 2007
     7 
     8 int s[N];
     9 int main()
    10 {
    11     int x=1;
    12     for (int i=1;i<=N-10;i++)
    13     {
    14       x=(x*5)%mod;
    15       s[i]=x;
    16     }
    17     int T,n;
    18     scanf("%d",&T);
    19     while (T--)
    20     {
    21       scanf("%d",&n);
    22       printf("%d\n",(n*4*s[n-1])%mod);
    23     }
    24     return 0;
    25 }

转载于:https://www.cnblogs.com/konjak/p/6071090.html

发表评论取消回复

表情：

评论列表（有 0 条评论，150人围观）

还没有评论，来说两句吧...

相关阅读

相关数论——因子组合

数论——因子组合【幸运数字】 `记录一道关于数论的题目，题目本身不难，主要是学习一下思想~` -------------------- 文章目录数论——

╰+哭是因爲堅強的太久メ/ 2024年03月30日 11:48/ 0 赞/ 47 阅读

相关数论——组合数学入门

排列组合 > 排列就是指从给定个数的元素中取出指定个数的元素进行排序；组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。--------OI Wiki

一时失言乱红尘/ 2024年03月17日 09:08/ 0 赞/ 70 阅读

相关回溯组合排列生成 LeetCode

回溯组合排列生成算法题目 [77. 组合][77.] 给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。示例: 输入:

╰半橙微兮°/ 2022年10月29日 04:26/ 0 赞/ 182 阅读

相关排列组合

排列组合问题： 1. 字符串全排列(permutation) 转自：[http://www.cnblogs.com/sujz/archive/2011/06/16/20828

我不是女神ヾ/ 2022年09月17日 06:27/ 0 赞/ 244 阅读

相关 BZOJ 2463: [中山市选2009]谁能赢呢？

2463: \[中山市选2009\]谁能赢呢？ Time Limit: 10 Sec Memory Limit: 128 MB Submit: 1407 Solved

港控/mmm°/ 2022年07月29日 08:43/ 0 赞/ 81 阅读

相关全排列、排列、排列组合

排列组合问题小总结：排列组合方法 1、for循环层层枚举 2、交换递归全排列 /给出

一时失言乱红尘/ 2021年12月20日 02:15/ 0 赞/ 399 阅读

相关【bzoj 2467】[中山市选2010]生成树（数论--排列组合）

题目：有一种图形叫做五角形圈。一个五角形圈的中心有1个由n个顶点和n条边组成的圈。在中心的这个n边圈的每一条边同时也是某一个五角形的一条边，一共有n个不同的五角形。这些五角形只

港控/mmm°/ 2021年12月17日 07:21/ 0 赞/ 151 阅读

相关 BZOJ1977/LuoguP4180【模板】严格次小生成树[BJWC2010] （次小生成树）

这道题本身思维难度不大，但综合性强，细节多在其上浪一个早上，你的最小生成树树链剖分线段树 DEBUG能力... 都大幅提升细节与思路都在代码里面了。

小鱼儿/ 2021年11月17日 05:10/ 0 赞/ 190 阅读

相关排列组合

1.引言 pku的OJ平台1731题，就是求一个输入字符串的全排列。在STL中有两个和排列相关的算法，next\_permutation和prev\_per

以你之姓@/ 2021年10月16日 00:14/ 0 赞/ 525 阅读

相关 BZOJ1835 [ZJOI2010] 基站选址【动态规划】【线段树】

题目分析：首先想一个DP方程，令f\[m\]\[n\]表示当前在前n个村庄选了m个基站，且第m个基站放在n处的最小值，转移可以枚举上一个放基站的村庄，然后计算两个村庄之间的

约定不等于承诺〃/ 2021年09月30日 03:16/ 0 赞/ 301 阅读