这个题是选择多个数字 使得其乘积是一个完全平方数。
本来以为是背包问题。 但是对于每一个数字要保存其前面的所有结果， 就不可能是背包了。
解析是 用了矩阵。 自己看了好长时间才明白咋回事。
先分解质因数。 把每个数字写成质因数乘积的形式。 然后根据矩阵变换...
1-25 1,165 views
阅读全文 0
这个题是一个图。 对于每一个点的 期望访问次数。 必然是由上一个节点的期望次数来决定。
那么 设 第i个点的访问次数为 Xi 然后根据前继节点 来表示 当前节点。
自然就会出现一个方程组。 高斯消元求方程组。
注意方程组无解的情况。 即（i，i）项的系数为 0，并且...
1-24 1,525 views
阅读全文 0
捣鼓了好几个小时的中国剩余定理。 终于弄明白了什么事了。。 其实明白之后才恍然大悟原来如此简单。。
查阅了好几本书。 但是 语言都晦涩难懂。。 特别是算法竞赛入门经典训练指南。。 表示没太懂。
这个比较好 http://www.cnblogs.com/walker01/archive/2010/01...
12-22 879 views
阅读全文 0
这个题自己一步步的写下去就会发现。 结果是sum（C（n，i）*a【i】）/（2^n-1）.
对于 2^n 以及很大的 C（n，i） 必然直接求 不可能。 那么就用到了 取对数了。 把每一项拆开。 我们可以得到。
exp(log(a[i])+temp-(n-1)*log(2)）；
利用 log c(n,k+1)-log c(n,k)=l...
12-17 800 views
阅读全文 0