题目名称 2369. [BZOJ 3456] 城市规划
输入输出 bzoj_3456.in/out
难度等级 ★★★★
时间限制 1500 ms (1.5 s)
内存限制 256 MiB
测试数据 10
题目来源 GravatarFoolMike 于2017-02-16加入
开放分组 全部用户
提交状态
分类标签
FFT
分享题解
通过:40, 提交:125, 通过率:32%
GravatarFoolMike 100 3.243 s 9.29 MiB C++
GravatarKirin 100 3.426 s 6.29 MiB C++
GravatarKirin 100 3.435 s 6.29 MiB C++
GravatarKirin 100 3.441 s 6.29 MiB C++
Gravatar梦那边的美好ET 100 3.467 s 9.16 MiB C++
GravatarAntiLeaf 100 3.519 s 5.29 MiB C++
GravatarAntiLeaf 100 3.562 s 6.29 MiB C++
Gravatar支羽 100 3.950 s 8.39 MiB C++
Gravatarpoorpool 100 3.969 s 6.80 MiB C++
Gravataryicongli 100 4.003 s 171.97 MiB C++
关于 城市规划 的近10条评论(全部评论)
为防止变成卡常大赛,把时限提高50%,由1s变为1.5s
GravatarAAAAAAAAAA
2017-12-21 21:40 8楼
$n \log^2 n$神TM卡常数
Gravatar小一米
2017-06-29 19:26 7楼
虚死了虚死了= =。
指数取模取mod-1重要的话说好几遍!
Gravatar半汪
2017-02-26 08:51 6楼
方案数mod 1004535809(479 * 2 ^ 21 + 1)
GravatarSky_miner
2017-02-19 07:02 5楼
你们真是卡的一手好常...
Gravatarstdafx.h
2017-02-18 22:08 4楼
代码常数大
GravatarYGOI_真神名曰驴蛋蛋
2017-02-17 20:23 3楼
回复 @Alboi_真神名曰蛋蛋 :
我找的标程一个点能跑到0.4s,所以我就开了1s时限
rank1的那个代码就是我找的标程- -
GravatarFoolMike
2017-02-17 13:47 2楼
我从网上找的标程验过了数据
GravatarFoolMike
2017-02-16 14:08 1楼

2369. [BZOJ 3456] 城市规划

★★★★   输入文件:bzoj_3456.in   输出文件:bzoj_3456.out   简单对比
时间限制:1.5 s   内存限制:256 MiB

【题目大意】

求含有 $n(n\le 130000)$ 个点有标号的无向联通图的个数(没有重边)。

方案数对 $1004535809(479\times 2^{21}+1)$ 取模。

【样例输入】

3

【样例输出】

4

【来源】

BZOJ 3456 城市规划