1430: 小猴打架

1430: 小猴打架

Time Limit: 5 Sec  Memory Limit: 162 MB

Submit: 335  Solved: 241

[Submit][Status]

Description

一开始森林里面有N只互不相识的小猴子,它们经常打架,但打架的双方都必须不是好朋友。每次打完架后,打架的双方以及它们的好朋友就会互相认识,成为好朋友。经过N-1次打架之后,整个森林的小猴都会成为好朋友。 现在的问题是,总共有多少种不同的打架过程。 比如当N=3时,就有{1-2,1-3}{1-2,2-3}{1-3,1-2}{1-3,2-3}{2-3,1-2}{2-3,1-3}六种不同的打架过程。

Input

一个整数N。

Output

一行,方案数mod 9999991。

Sample Input

4

Sample Output

96

HINT

50%的数据N<=10^3。 100%的数据N<=10^6。

Source

 题解:额。。。这貌似是我除了bzoj1000之外最短的bzoj程序了。。。这个题我首先看到了“小猴打架”这个词,然后又看到了“打一次架后双方成为朋友”,乍一下想到了并查集,可是当我看到有多少种打法时我发现我想多了。。。显然,对于N个节点的生成树,种类有N^(N-2),因为这道题看样子对与打架顺序还要重复计算,所以再来个N!/N,也即是(N-1)!,所以F(x)=(x-1)!*x^(x-2)(呵呵呵呵呵机智的我连快速幂都懒的写了么么哒)

1 const p=9999991;
2 var i,j,k,m,n:longint;l:int64;
3 begin
4      readln(n);l:=1;
5      for i:=1 to n-2 do l:=(l*n) mod p;
6      for i:=(n-1) downto 1 do l:=(l*i) mod p;
7      writeln(l);
8 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏聊聊技术

原 数据结构-散列表(Hash Table

3579
来自专栏HansBug's Lab

1293: [SCOI2009]生日礼物

1293: [SCOI2009]生日礼物 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1096  Solv...

2777
来自专栏小樱的经验随笔

BZOJ 1293: [SCOI2009]生日礼物【单调队列】

1293: [SCOI2009]生日礼物 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 2534  Solv...

2635
来自专栏Django中文社区

Django 博客文章自动生成摘要的两种方法

首页的博客文章列表通常需要显示摘要,Django 有两种方法来实现这个需求。 复写 save 方法 第一种方法是通过复写模型的 save 方法,从正文字段摘取前...

36910
来自专栏程序员同行者

django 模型关系

比如汽车和制造商的例子,一辆汽车只能属于一个制造商,但是一个制造商有多辆汽车,这个关系,用Django的Model来表示,就是

933
来自专栏大前端_Web

深入理解xhr的responseType中blob和arrayBuffer

版权声明:本文为吴孔云博客原创文章,转载请注明出处并带上链接,谢谢。 https://blog.csdn.net/wkyseo/articl...

2644
来自专栏HansBug's Lab

3224: Tyvj 1728 普通平衡树

3224: Tyvj 1728 普通平衡树 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 2566  Sol...

3586
来自专栏salesforce零基础学习

salesforce 零基础学习(六十八)http callout test class写法

此篇可以参考: https://developer.salesforce.com/docs/atlas.en-us.apexcode.meta/apexcode...

3097
来自专栏C/C++基础

Linux命令(12)——wc命令

(3)从文件读取输入文件名。如果有多个文件名,并且希望 wc 从一个文件中读取它们,那么使用-files0-from 选项。这里将文件名称必须以NULL字符结束...

1081
来自专栏互联网高可用架构

伪共享和缓存行

1612

扫码关注云+社区

领取腾讯云代金券