题意:有一个长度为m的环,从0~m-1,有n只青蛙,每只青蛙每次可以跳Ai步,跳到一个位置之后就标记一下,问最后所有标记出来的位置的和。

思路:对于Ai步的青蛙来说,他所经过的位置就是gcd(m, Ai)的倍数。

那么对于所有的青蛙来说,就是容斥一下,预处理出所有的gcd之后,假设两个数 a, b 所经过的位置就是 a的倍数+b的倍数-lcm(a,b)的倍数。

然后就可以愉快的容斥了。一开始写的时候用的二进制枚举子集。。一直WA啊。。 完全找不出错哪里。后来知道了gcd的个数可以达到70+ ,1<<70溢出了。

10^9 > 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19, 假设gcd是C(8,2) 都28了。所以很大。要dfs就可以防止溢出的问题。

但是直接dfs会TLE, 2^n的复杂度(n是gcd的个数),还要加剪枝,如果当前的lcm是gcd[i]的倍数,那么可以不继续容斥下去。

因为 lcm所占的位置,一定在gcd[i]里面。

 

Codeforces Round #317 (Div. 1) Lengthening Sticks(容斥+暴力)

题意:给你一个三角形的三边长a,b,c和一个长度L,问你把L添加到a,b,c上去,有多少种方法可以组成三角形。 思路: 1. 求组成三角形的个数,可以用所有可能的...

阅读全文

HDU 4790 Just Random(容斥 + 数学推导 + 规律)

题意:从[a,b]内选一个数x,从[c,d]内选一个数y,问有多少对(x+y)%p = m。 思路:因为第一个区间和第二个区间是不同的。所以让他尽量相同,可以利用容斥原理...

阅读全文

2015 Multi-University Training Contest 1 HDU-5297 Y sequence(容斥原理)

题意:给定一个r值,每次可以从1-无穷里面删除所有a^( 2~r)的数,求在删除之后,可以得到的第n个数。 思路:还是比较容易想到是容斥原理的,首先对于一个序列...

阅读全文

3 条评论

  1. 想问下博主,一开始是怎么知道这样的方法可行的?就是怎么计算出这样的算法的复杂度能满足题意?

    1. dfs的剪枝都是玄学,不好算,只能尝试性的剪一剪,这个题现场出的,都是直接暴力过去的,没有剪枝。

欢迎留言

*