某島

… : "…アッカリ~ン . .. . " .. .
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 個。。那麼肯定不滿足。。所以搜索的過程,對每組數,就只有保留和不保留兩種決策了。。
搜索的每一步都假設後面的數全部刪除。。逐步保留一些數字。。累計答案即可。。