0w1

Combanitorics

AGC 12 D - Colorful Balls ( Math, Combination )

D: Colorful Balls - AtCoder Grand Contest 012 | AtCoder題意: 有若干個球排成一排,第 i 個球用顏色 C[ i ],重量 W[ i ] 描述。可以進行的操作有兩種: 1. 選擇兩個相異位置的相同顏色的球,若它們的重量和不超過 X,將它們交換位置 2. 選擇兩個相異位…

Yuki 389 ロジックパズルの組み合わせ ( Combinatorics, Math )

No.389 ロジックパズルの組み合わせ - yukicoder題意: 在一排 M 個格子上放黑色點,依序為 H[ 0 ], H[ 1 ] .. H[ N ] 個連續的黑色點,且兩兩以至少一個的連續白色點區隔。求模 1e9 + 7 後的方案數。資料規模: 1 ≤ M 0 ≤ H[ i ] SIGMA{ H } ≤ M 保證若有一…

CFR 559 C. Gerald and Giant Chess ( DP )

Problem - C - Codeforces題意: 在一個棋盤上,起點 ( 1, 1 ) 終點 ( H, W ),給若干個禁止點,求不走遠路的路徑數,不經過禁止點,其餘數。資料規模: 1 ≤ H, W ≤ 1e5 禁止點數 1 ≤ N ≤ 2000解法: 預處理階乘表後,可以用組合公式 ( H + W ) ! / ( H ! * …