Balkan 2007 简明解题报告
30/01/2009Day I
Cipher
好像应该拿Hash做吧, 标程写的很离奇, 看不懂凭什么可以这么做. 自己也没能写出一个可以AC的程序.
Dream
一道组合数学的题. 分析题目, 实际上是要我们从第一个盒子和最后一个盒子中取一个数, 其他盒子取两个数, 使乘积可以被k整除, 问有多少种方案.
首先求出k的所有因子集合S, 再为盒子中每一个数a在S中找到最大的数b使a mod b = 0. 这两个都需要预处理掉, 还有一个next[a][b]数组, 表示若一个数是k的第a和第b个因子的公倍数, 则它在S中最大的因子是第next[a][b]个因子. 之所以要最大, 在后面的运算中, 方案会优先累计到最大的因子, 即k本身上.
我们用total[a][b]表示到第a行为止, 累计到多少种方案可以使取数之乘积可以被k的被b个因子整除, 需要注意的是, 这里只是累计到的方案, 也就是实际的方案可能比累计到的多, 正如我们之前提到的, 如果某种方案所得到的乘积既能被第a个因子整除, 又能被第b个因子整除, 那么会优先记在记b个因子所表示的total单元中, 即较大的因子头上(假设b>a). 我们先用累加的方法统计第一个盒子中的数字可以被哪个因子整除. 从第二行开始, 先统计单这一行得到的乘积可以被哪个因子整除, 之后再根据乘法原理计到total数组中去. 具体的说, 先用cur1表示只取一个数时可以被哪个因子整除(当然要尽可能大的因子), cur2表示取两个数后乘积可以被哪个因子整除(自然也要尽可能大的因子), cur1用与求第一个盒子相同的方法求出, 再枚举两个因子a,b, 若是相同的因子, 则cur2的next[a][b]单元(即乘积的最大因子)累加cur1[a]*(cur[a]-1) (乘法原理), 若不相同, 则cur2的next[a][b]单元累加cur1[a]*cur1[b]*2 (两种不同的取数顺序). 注意最后一行就不需要这样分两步统计了. 然后再用类似的方法将统计结果累加入total数组中就可以了(再具体的见代码吧).
我的代码写的比较丑, 官方解答写的很漂亮, 看一下就明白了.