静安企业网站建设,制作公司网页官网,兼职招聘网站,广州网站建设粤icp星际之门#xff08;一#xff09; 时间限制#xff1a;3000 ms | 内存限制#xff1a;65535 KB难度#xff1a;3描述公元3000年#xff0c;子虚帝国统领着N个星系#xff0c;原先它们是靠近光束飞船来进行旅行的#xff0c;近来#xff0c;X博士发明了星际之门一 时间限制3000 ms | 内存限制65535 KB 难度3 描述 公元3000年子虚帝国统领着N个星系原先它们是靠近光束飞船来进行旅行的近来X博士发明了星际之门它利用虫洞技术一条虫洞可以连通任意的两个星系使人们不必再待待便可立刻到达目的地。 帝国皇帝认为这种发明很给力决定用星际之门把自己统治的各个星系连结在一起。 可以证明修建N-1条虫洞就可以把这N个星系连结起来。 现在问题来了皇帝想知道有多少种修建方案可以把这N个星系用N-1条虫洞连结起来 输入第一行输入一个整数T,表示测试数据的组数(T100) 每组测试数据只有一行该行只有一个整数N表示有N个星系。(2N1000000)输出对于每组测试数据输出一个整数表示满足题意的修建的方案的个数。输出结果可能很大请输出修建方案数对10003取余之后的结果。样例输入 2
3
4 样例输出 3
16 来源[张云聪]原创上传者 张云聪 我也不清楚为毛线这一道题为什麽会出现在图论中大概是证明过程参考大神的证明 简单点说就是 一一对应法 假定T是其中一棵树树叶中有标号最小者设为a1a1的邻接点为b1从图中消去a1点 和边(a1, b1).b1点便成为消去后余下的树T1的顶点.在余下的树T1中寻找标号最小的树叶设 为a2a2的邻接点为b2从T1中消去a2及边(a2, b2).如此步骤继续n-2次直到最后剩下一条 边为止.于是一棵树T对应一序列 b1,b2,…,b[n-2] 恢复树T 序列I 1,2,…n 序列II b1,b2,…,b[n-2] 在I中找出第一个不出现在II中数显然是a1连接边(a1, b1)在I中消去a1在II中消 去b1.如此步骤重复n-2次序列I中两个数构成最后一条边. 以下是来自Matirx67的blog. ayley公式是说一个完全图K_n有n^(n-2)棵生成树换句话说n个节点的带标号的无根树有n^(n-2)个。Cayley公式的一个非常简单的证明证明依赖于Prüfer编码它是对带标号无根树的一种编码方式。 给定一棵带标号的无根树找出编号最小的叶子节点写下与它相邻的节点的编号然后删掉这个叶子节点。反复执行这个操作直到只剩两个节点为止。由于节点数n2的树总存在叶子节点因此一棵n个节点的无根树唯一地对应了一个长度为n-2的数列数列中的每个数都在1到n的范围内。下面我们只需要说明任何一个长为n-2、取值范围在1到n之间的数列都唯一地对应了一棵n个节点的无根树这样我们的带标号无根树就和Prüfer编码之间形成一一对应的关系Cayley公式便不证自明了。 看到这我建议自己划一划结果就出来了这句话是我的建议非Matrix67原文。 注意到如果一个节点A不是叶子节点那么它至少有两条边但在上述过程结束后整个图只剩下一条边因此节点A的至少一个相邻节点被去掉过节点A的编号将会在这棵树对应的Prüfer编码中出现。反过来在Prüfer编码中出现过的数字显然不可能是这棵树初始时的叶子。于是我们看到没有在Prüfer编码中出现过的数字恰好就是这棵树初始时的叶子节点。找出没有出现过的数字中最小的那一个比如④它就是与Prüfer编码中第一个数所标识的节点比如③相邻的叶子。接下来我们递归地考虑后面n-3位编码别忘了编码总长是n-2找出除④以外不在后n-3位编码中的最小的数左图的例子中是⑦将它连接到整个编码的第2个数所对应的节点上例子中还是③。再接下来找出除④和⑦以外后n-4位编码中最小的不被包含的数做同样的处理……依次把③⑧②⑤⑥与编码中第3、4、5、6、7位所表示的节点相连。最后我们还有①和⑨没处理过直接把它们俩连接起来就行了。由于没处理过的节点数总比剩下的编码长度大2因此我们总能找到一个最小的没在剩余编码中出现的数算法总能进行下去。这样任何一个Prüfer编码都唯一地对应了一棵无根树有多少个n-2位的Prüfer编码就有多少个带标号的无根树。 一个有趣的推广是n个节点的度依次为D1, D2, …, Dn的无根树共有(n-2)! / [ (D1-1)!(D2-1)!..(Dn-1)! ]个因为此时Prüfer编码中的数字i恰好出现Di-1次。 #includestdio.h
#includestring.h
#includealgorithm
using namespace std;
#define M 10003
long long mod(int a,int b,int c)
{int t1;if(b0)return 1;if(b1)return a%c;tmod(a,b1,c);tt*t%c;if(b1)tt*a%c;return t;
}
int main()
{int t;scanf(%d,t);while(t--){int m;scanf(%d,m);long long smod(m,m-2,M);printf(%lld\n,s);}return 0;
}转载于:https://www.cnblogs.com/playboy307/p/5273503.html
