#P3456. 城市规划
城市规划
城市规划
题目描述
阿狸的国家有 个城市,编号为 到 。国家要在一些不同的城市对之间修建双向贸易路线,使得任意两个城市都可以通过一条或多条路线相互到达。每对城市之间至多修建一条直接路线。
如果有一对城市在两个方案中是否直接相连的情况不同,这两个方案就是不同的。求可行方案的数量,也就是 个带编号顶点的无向简单连通图的数量,对 取模。
输入格式
输入一行一个整数 ,。
输出格式
输出一行一个整数,表示方案数取模后的值。
样例 #1
3
4
阿狸的国家有 n 个城市,编号为 1 到 n。国家要在一些不同的城市对之间修建双向贸易路线,使得任意两个城市都可以通过一条或多条路线相互到达。每对城市之间至多修建一条直接路线。
如果有一对城市在两个方案中是否直接相连的情况不同,这两个方案就是不同的。求可行方案的数量,也就是 n 个带编号顶点的无向简单连通图的数量,对 1004535809=479×221+1 取模。
输入一行一个整数 n,1≤n≤130000。
输出一行一个整数,表示方案数取模后的值。
3
4