Gravatar
再见
积分:2248
提交:518 / 978
回复 @FoolMike :
发现挂的原因了,树太深了,按我的算法概率太小直接崩掉了。(我需要算所有点一直爬到环上点的概率)
还有这道题暴力其实只能拿20分,树深了概率直接近似0了。。。。。
不想调了,感觉写的好恶心。。。

Gravatar
FoolMike
积分:5199
提交:1165 / 2240
回复 @sherc :
我只写了50分的树,懒得写基环树了。这题在考场上感觉不敢写正解的样子。

Gravatar
kZime
积分:1101
提交:334 / 677
手写队列写挂了,调了大半年。。。。

Gravatar
pα.Princesavs
积分:210
提交:100 / 122
...考试的时候咋没想到累5orz

题目 2672 [HAOI 2017]方案数
2017-05-09 16:02:35
Gravatar
Troywar
积分:742
提交:223 / 455
int 转 longlong玩死自己=-=

Gravatar
HZOI_蒟蒻一只
积分:1514
提交:319 / 790
时间可以小于-1……
身败名裂……
事实证明,初始化搞成很小的负数是很必要的……

Gravatar
小字、小瓶子
积分:437
提交:175 / 311
数组开到1125751就行了

题目 7 通信线路 AAAAAAAAAA
2017-05-09 01:01:56
Gravatar
FoolMike
积分:5199
提交:1165 / 2240
第一次把范围看成2e6,于是吓得我赶紧写FFT,后来发现FFT可以过2e6的数据,但是内存得大一点……

Gravatar
再见
积分:2248
提交:518 / 978
当我写环算法时写恶心的时候,就知道环应该爆0了。。

Gravatar
Fisher.
积分:933
提交:301 / 521
long long

Gravatar
sxysxy
积分:2485
提交:603 / 1120
总共用时0.2s,一个点竟然给5s,我觉得有必要把时限限制得稍紧一些
======我是分割线=====
E,X两个字母就是用两个颜色对物体染色,物体置换群G = {转0格,转1格,...,转(n-1)格},对于每一个置换 $g$,拆解得循环节个数为 $c(g)$,容易发现转 $k$格的置换$ g_{k} $ 的循环节个数 $ c(g_{k}) = gcd(k, n) $ 直接套用polya定理,最后答案就是
$ \frac{1}{n} \sum_{k=0}^{n-1} 2^{gcd(k, n)} $
然后我这么快的高精度运算模板都还是TLE了,于是我们对于$ \frac{1}{n} $右边的式子继续进行化简
$ \sum_{i=0}^{n-1} 2^{gcd(i, n)} $
$ = \sum_{d|n}^{ } \sum_{i=1}^{n} 2^{gcd(i, n)} [gcd(i, n) == d] $
$ = \sum_{d|n}^{ } \sum_{i=1}^{n} 2^{gcd(\lfloor \frac{i}{d} \rfloor,\lfloor \frac{n}{d} \rfloor)} [gcd(\lfloor \frac{i}{d} \rfloor,\lfloor \frac{n}{d} \rfloor) == 1] $
熟悉积性函数那套理论的同学一眼就看出了每个约数d对答案的贡献为$ 2^d \phi(\frac{n}{d})$
最后答案就是$ \frac{1}{n} \sum_{i|n}^{ } 2^i \phi(\frac{n}{i}) $
=====我是分割线=====
压位+FFT一块使用,效果惊人

Gravatar
sxysxy
积分:2485
提交:603 / 1120
压位+FFT,0.171s...

Gravatar
神犇
积分:0
提交:0 / 1
回复 @AntiLeaf :
呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃

Gravatar
~玖湫~
积分:911
提交:251 / 418
tarjan缩点+树包

Gravatar
HZOI_蒟蒻一只
积分:1514
提交:319 / 790
回复 @hzoi_LadyLex :
l==r了,就不用再交换了,反正就这一个数

Gravatar
ztzshiwo
积分:127
提交:65 / 142
这个题要LL吗

Gravatar
test
积分:1074
提交:380 / 1216
Tarjan+SPFA+dp

题目 2682 膜拜 AAAAAAAAAAAAAAAA
2017-05-06 20:43:49
Gravatar
FoolMike
积分:5199
提交:1165 / 2240
暴力好像跑过了……

Gravatar
FoolMike
积分:5199
提交:1165 / 2240
这常数也能卡过?复杂度不应该是O(n^3*logans)或O(n^2*logans)级别的吗?

Gravatar
再见
积分:2248
提交:518 / 978
写代码最丑的一回。。。一行80个字符,其中50多个都是MOD,+MOD%MOD的。。。。