TopCoder SRM527 P8XCoinChange

2016.03.29 20:37 Tue| 21 visits oi_2016| 2016_刷题日常| Text

题目大意

有 n(n≤40) 种硬币,面值为 a[0]~a[n-1](a[i]≤1018、a[i]<a[i+1]),每种个数不限。满足 a[0]=1,且对于任意 i<j,a[i] 是 a[j]的约数。求用这些硬币得到面值和 s(s≤1018) 的方案数。

算法分析

题目相当于求从数轴原点出发,每一次可以往后跳 a[i] 的距离且跳跃距离单调不增,最终跳到点 s 的方案数。

对于一段区间,构造矩阵 M,令它的第 i 行第 j 列 M(i,j) 表示第一步的距离不大于 a[i],最后跳的一步的距离是 a[j] 的方案数。

发现由于每一次跳跃的长度不尽相同,不能直接构造上述矩阵进行转移,但我们可以发现,无论如何跳跃,有一些点总会被经过,且相邻两个必经点间距离一定等于 a[x](0≤x<n)。对于 a 中的每一个元素,预处理出跳跃相应距离的方案数,之后随随便便转移一下即可。

代码

1
  • 15195424882017-01-04 20:58

    这里有一道不取模的题目

    http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1167