某岛

… : "…アッカリ~ン . .. . " .. .
August 22, 2012

Codeforces Round #134

(A 略。B 给定一组一种类 斐波那契数的构造方式,每一步可以选 F[n] = F[n-1] + F[n-2] 或者 F[n] = k F[n-1] + F[n-2]。。。要求通过 n 次构造得到数 r,要求采取第二种策略最少。。。。(D: 给定 N 个数。。问从中可以有多少种集合可以使得集合中的数可以 % M = 0。。(限制方程组的系数只可以取 {-1, 1}。。(E: Rope ?。Splay ?。。。。

Brief description:

Problem D:
给定 n 个数,问有多少个子集,使得从这 n 个数中取出这些数之后,余下的数组成的 +-1 组合无法模 P 为 0。
( n <= 10000, p <= 120 ... )

Analysis:

.. 暴搜。。。实际上这个不是任何经典模型。。。。
突破口在于模数很小。。。首先考虑将模 P 相同(互为相反的也视为相同)的数分组。。
那么。。如果所有的数都选肯定是一种符合条件的方案。。(所以答案至少为 1.。。
接着对同一组如果残余 2 个。。那么肯定不满足。。所以搜索的过程,对每组数,就只有保留和不保留两种决策了。。
搜索的每一步都假设后面的数全部删除。。逐步保留一些数字。。累计答案即可。。