0w1

Pigeon hole principle

CFR 367 E. Sereja and Intervals ( Segment Trick DP + Pigeon Hole Principle )

Problem - E - Codeforces題意: 在 [ 1, M ] 中,要算有多少種方法,可以有 N 個有序區間( ex: { [ 1, 2 ], [ 3, 4 ] } != { [ 3, 4 ], [ 1, 2 ] } ),不存在任一個區間包含另一個區間,且有至少一個區間的左界為 X,求其餘數。數據範圍: 需要區間數,值域…

POJ 3260 The Fewest Coins ( Knapsack multiple & complete DP )

3260 -- The Fewest Coins n ≤ 100 types of currency exists, each value v[i] ≤ 120, and I have c[i] ≤ 100 of them. Answer the minimum sum of coins that I have to give and take, when I am to buy a product of T ≤ 10000 dollars. This is basical…

Hacking hash algorithms on string with birthday attack

Many people are familiar with hash algorithms on string because they are easy to write. However, not many are really aware of the probability of collision. Like me, I had always thought the probability of collision is ( 1 / MOD ), and I ha…