Gravatar
kZime
积分:1101
提交:334 / 677
額?就一個點?

题目 1570 [POJ 3461] 乌力波 A
2017-05-18 10:23:32
Gravatar
BaDBoY
积分:1201
提交:399 / 1113
最后需要处理一下重复的出现,否则不对,f[i][j]表示选取哪几个数(当前状态)余数为j,转移方程 f[i | (1<<k)][(j * 10 + s[k]) % d] += f[i][j]  ((i & (1<<k)) == 0) ,最后应输出f[1<<(len-1)][0]处理重复出现后的ans(排列数)

题目 2408 [SCOI 2007]排列
2017-05-18 10:17:48
Gravatar
HZOI_蒟蒻一只
积分:1514
提交:319 / 790
我不服,为什么Dijkstra这么慢

Gravatar
FoolMike
积分:5199
提交:1165 / 2240
只分一次块,复杂度是O(n^(3/4))的吗?

Gravatar
sxysxy
积分:2485
提交:603 / 1120
我太弱了,打一下我的70分做法quq:
$ \sum_{i=1}^{n} \sum_{j=1}^{m} \phi(gcd(i, j)) $
$ = \sum_{d=1}^{n} \sum_{i=1}^{n} \sum_{j=1}^{m} \phi(gcd(i, j)) [gcd(i, j) == d]$
$ = \sum_{d=1}^{n} \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} \phi(d*gcd(\frac{i}{d}, \frac{j}{d})) [gcd(\frac{i}{d}, \frac{j}{d}) == 1]$
$ = \sum_{d=1}^{n} \phi(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} [gcd(\frac{i}{d}, \frac{j}{d}) == 1]$
设$ F(n, m) = \sum_{i=1}^{n} \sum_{j=1}^{m} [gcd(i, j) == 1]$
则原式
$ = \sum_{d=1}^{n} \phi(d) F(\lfloor \frac{n}{d} \rfloor, \lfloor \frac{m}{d} \rfloor)$
F的计算参见 HAOI2011 问题B
分块优化,单次查询时间复杂度应该是接近O(n)的?
Orz

Gravatar
sxysxy
积分:2485
提交:603 / 1120
一开始没看见F(1) = 0。按一般的约数个数函数推了,后来发现了,一慌:读错题了,但是忽然想到F(1) = 0不过是把gcd == 1的贡献减去了而已。。。写一下推的过程:
设 $ D(x) = \sum_{d|x}^{ } 1 $ 也就是x的约数的个数。(与本题中F的区别就是$ D(1)=1 $)
$ \sum_{i=1}^{n} D(gcd(i, n)) = \sum_{d|n}^{ } \sum_{k=1}^{\lfloor \frac{n}{d} \rfloor} D(d) [gcd(k, \frac{n}{d}) == 1] $
$ = \sum_{d|n}^{ } D(d) * \sum_{k=1}^{\lfloor \frac{n}{d} \rfloor} [gcd(k, \frac{n}{d}) == 1] $
$ = \sum_{d|n} D(d) * \phi(\frac{n}{d})$
发现是个狄利克雷卷积的形式,我们先变换一下:(下面这个$ * $表示狄利克雷卷积运算)
$ = D * \phi$ = $ 1 * 1 * \phi$ = $ id * 1$
到这里求解就非常容易了,就是
$ = \sum_{d|n} \frac{n}{d} $
那原题里面不是D函数,而是F,区别在于$ F(1) = 0 $,怎么办
注意到原式子 $\sum_{i=1}^{n} F(gcd(i, n))$ ,我们求出来的是 $ \sum_{i=1}^{n} D(gcd(i, n))$,只有$ gcd(i, n) == 1 $ 的时候,F和D有偏差。
对于每一个$ gcd(i, n) == 1 $ ,我们都刚好多算了$ 1 $,所以最后我们答案多算了$ \phi(n) $,减去即可。
最终
$ Ans = \sum_{d|n} \frac{n}{d} - \phi(n) $
可以在$ O(\sqrt{n})$ 的时间复杂度内求解出来。

Gravatar
JustWB
积分:619
提交:222 / 519
倒数第二个测试点什么鬼嘛.......
我选择打表.........
想着既然打表就打的爽快一点然后就借了@He 的快读.......
然后怎么就跑第一了........

题目 2451 宗教信仰 AAAAAAAAAA
2017-05-17 21:49:01
Gravatar
沧澜
积分:334
提交:149 / 368
AAAAAAA

Gravatar
沉迷太阳的向日葵
积分:34
提交:12 / 19
文件名打错了!?两次都不过,心态炸了

Gravatar
kZime
积分:1101
提交:334 / 677
我好水啊qwq

题目 602 新的开始 AAAAAAAAAA
2017-05-17 20:01:53
Gravatar
kZime
积分:1101
提交:334 / 677
我好水啊qwq

Gravatar
sxysxy
积分:2485
提交:603 / 1120
下面是题解:(白色的字体,选中即可看到)
维护一个滑动矩形内的权值和,这个矩形的宽度是固定R-L+1的,因此我们把矩形 [i-R, i-L] 这一段直接合并了就好了,然后 一般的线段树/树状数组 就可以维护了,并不需要可持久化数据/树套树等。

Gravatar
HZOI_蒟蒻一只
积分:1514
提交:319 / 790
看这题看了半年了,终于过了……想死……
PS:果然后做有好处,地雷都被踩完了……

Gravatar
HZOI_蒟蒻一只
积分:1514
提交:319 / 790
正反dp是个玄学……

Gravatar
xzcxzc11
积分:149
提交:63 / 133
滑稽

Gravatar
Hzoi_Mafia
积分:1556
提交:331 / 773
回复 @Hzoi_Ivan :
我也是QWQ

Gravatar
HeHe
积分:1192
提交:426 / 866
线段树233

Gravatar
Hzoi_Ivan
积分:1148
提交:367 / 876
zzhzz

Gravatar
Hzoi_Hugh
积分:1279
提交:431 / 1224
zzh

Gravatar
Hzoi_Hugh
积分:1279
提交:431 / 1224
zzh

题目 2417 [HZOI 2016]在路上
2017-05-17 15:35:34