原创problem12宝石纪念币_第1页
原创problem12宝石纪念币_第2页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

宝石纪念币题解考虑这样一个子问题，用m不同颜色的宝石（不一定全用这可以利用Polya定理求解所有的置换共有n即顺时针一格两格…n顺时针旋转k的置换显然可以表示成(n,k1 (n,k个长为n的循环。因此，这个子问题的答案就是：nm (n,

k现在原问题要求的是恰好使用了17种颜色的宝石的方案数 17

m117 (n,k)故由容斥原理，答案为：n

mm m1 k 计算中的一些细节问题这里先这些问题后文就不再一一叙述（1）由于求和最后要除以n，所以应该保存答案modn10len的结果也就是说，高精度的最后len为都是mod10位，但第len+1位无法避免小减大。因此要。第len+1位要退n，而不是10，（3）120直接处理较长，可考虑为压缩，2一缩、3一缩、4位一缩都是可以考虑的，考虑到int64longint计算慢很多使用3一缩。，下介绍算法度为O(cn2len2。其中c颜色数17，len输出长度120。时间复杂度为O(clen2nlogn)。同的m循环一次，保留计算的结果，时间复杂度为O(cnlen2。算法（标准算法注意到对于不同的k(n,k)的值相等m(n,k的值也是相等的因此考虑统计有多少个k(nk的值为给定的正整数t。由于(nk)t

t|

，所以这样的kn个 tk,n tt tt n所以n

m(n,k

nmt k

t|n(k

注意到n是可以在O(d(n))时间内全部算出（其中d(n)表示 t ，于时间复杂度为O(clen2d(nlogn。对于3的时间来说是足够了。算法五：这里再给出一种DP的思路，尽管时间复杂度较高，但也能得一定的分数为1,2…n。再规定17种颜色出现的顺序。记DPi,j表示到位置i为止恰好出现j颜色的方案数。则可写出状态转移方程：注意到不涉及高精度与高精度乘法而只涉及高精度数与低度数的乘法，故计算所有DPi,j的时间复杂度为O(cnlen)不过需要注意的是，17!DPn,17不是最终的答案，因为循环的安n会导致重复计算。正确的方法是使用容斥原理。具体推导过程不再出，最后的公式是 n

。依旧不涉及高精度数与高精度nt

t 的乘法。总时间复杂度是O(cnlen)（在这个算法基础上，利用矩阵乘法可加速DP，但无法避免高精度数与高精度数的乘法时间复杂度O(c3lognlen2d

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论