BZOJ 4926: 皮皮妖的递推

###Description YOUSIKI学习了递推,于是他请皮皮妖给他出道题,皮皮妖说: f(1)=1,f(i)=i-f(i-1),求f(n) YOUSIKI看了一眼把它秒切了,于是他要求皮皮妖加大难度,皮皮妖想了想,说: f(1)=1,f(i)=i-f(f(i-1)),求f(n) YOUSIKI看了两眼把它秒切了,于是他要求皮皮妖加大难度,皮皮妖想了想,说: f(1)=1,f(i)=i-f(f(f(i-1))),求f(n) YOUSIKI看了三眼把它秒切了,于是他要求皮皮妖加大难度,皮皮妖想了想,说: ... ... ... YOUSIKI看了m眼,但是没有能...

Codeforces 809E. Surprise me!

###Description 给一棵树,每个点点权 $$a_i$$,保证 $$a_i$$各不相同,现在随机选两个点 $$u,v$$,求 $$f(u,v)=\phi(a_u\cdot a_v)\cdot dis(u,v)$$ 的期望,$$mod\ 10^9+7$$。 链接:[http://codeforces.com/contest/809/problem/E](http://codeforces.com/contest/809/problem/E "http://codeforces.com/contest/809/problem/E") ###Solution 首先,有...

SCOI 2017 酱油记

省选终于考完了啊。。 Day1: 先用10分钟浏览了一遍题 看了看t1,感觉贪心好像是对的啊,写了个堆搞一搞 再看t2,最近点似乎可以用点分,再加个树剖维护第一个未签到点,于是码码码,码完3.5h了 一看t3,卧槽计算几何啊。。写了发暴力。然后想到一个n^2sqrt的kd树做法,后来没调出来 最后230 Day2: 又先用10分钟浏览了一遍题 t1切了 t2是两道题加起来的,都可以O(n),然而我都只会nlog,于是T了40 t3写了一个能过大样例的n^2log暴力,但最后只得了10分。。orz 最后170 总分400,似乎挺靠前的

BZOJ 2694 & 4659 Lcm

###Description ![fa(1).jpg][1] ###Solution $$\sum_i^n\sum_j^m[\mu(gcd(i,j))\neq 0]lcm(i,j)$$ $$=\sum_k^n|\mu(k)|\sum_i^{\frac{n}{k}}\sum_j^{\frac{n}{k}}[gcd(i,j)=1]i\cdot j\cdot k$$ $$=\sum_k^n|\mu(k)|\cdot k\sum_d^{\frac{n}{k}}\mu(d)\cdot d^2\sum_i^{\frac{n}{k\cdot d}}\sum_j^{\frac{m}{k\c...

BZOJ 3926: [Zjoi2015]诸神眷顾的幻想乡

##Description 幽香是全幻想乡里最受人欢迎的萌妹子,这天,是幽香的2600岁生日,无数幽香的粉丝到了幽香家门前的太阳花田上来为幽香庆祝生日。 粉丝们非常热情,自发组织表演了一系列节目给幽香看。幽香当然也非常高兴啦。 这时幽香发现了一件非常有趣的事情,太阳花田有n块空地。在过去,幽香为了方便,在这n块空地之间修建了n-1条边将它们连通起来。也就是说,这n块空地形成了一个树的结构。 有n个粉丝们来到了太阳花田上。为了表达对幽香生日的祝贺,他们选择了c中颜色的衣服,每种颜色恰好可以用一个0到c-1之间的整数来表示。并且每个人都站在一个空地上,每个空地上也只有一个人。这...

对于各种并查集写法速度的研究

这个测试的全都是路径压缩,不按秩合并,不维护额外信息的并查集。 先放测试代码: ```c++ #include #include #define N 131072 #define T 1000 int fa[N],st[N]; int find1(int x) { return x==fa[x]?x:fa[x]=find1(fa[x]); } inline int find2(int x) { return x==fa[x]?x:fa[x]=find2(fa[x]); } inline int find3(int x) { w...

BZOJ 3160: 万径人踪灭

###Description 略。见[BZOJ3160][1] ###Solution 对于“不能是连续的一段”,可以先计算所有答案,然后减去连续一段的,即回文串,这个用回文自动机或者manacher可以得出 考虑以每个位置为中心的对称元素对个数f[i],那么i位置对答案的贡献是$$2^{f[i]}-1$$ 如果把a视为1,b视为-1,然后把原串长度\*4,卷积,那么以i为中心的元素对如果相同,则贡献1,否则贡献-1 ###Code ```c++ #include typedef double lf; #define fo0(i,n) for(int i=...

BZOJ 2989: 数列 & 4170: 极光

###Description 给定一个长度为n的正整数数列a[i]。 定义2个位置的graze值为两者位置差与数值差的和,即graze(x,y)=|x-y|+|a[x]-a[y]|。 2种操作(k都是正整数): 1.Modify x k:将第x个数的值修改为k。 2.Query x k:询问有几个i满足graze(x,i)

BZOJ 4750: 密码安全

###Description 有些人在社交网络中使用过许多的密码,我们通过将各种形式的信息转化为 01 信号,再转化为整数,可以将这个人在一段时间内使用过的密码视为一个长度为 n 的非负整数序列 A_1,A_2,...,A_n 。一个人相邻几次在社交网络中使用的密码很有可能是类似的,这使得密码并不是足够安全。为了检验某些人在某些时间段内是否可能受到不安全的影响,我们需要计算上述序列的复杂程度。 ![aa.jpg][1] 的值,这将作为我们评估密码复杂程度的一个部分。由于答案可能很大,你只需要给出答案对10^9+61 取模的值即可。 ###Input 第一行包含一个正整数 T...

BZOJ 2958&3269: 序列染色

###Description 给出一个长度为N由B、W、X三种字符组成的字符串S,你需要把每一个X染成B或W中的一个。 对于给出的K,问有多少种染色方式使得存在整数a,b,c,d使得: 1