0w1

Combanitorics

Yuki 589 Counting Even

Problem Description: Given a non-negative integer N, find the number of i, such that C(N, i) % 2 == 0 and 0 ≤ i ≤ N.Constraints: 0 ≤ N ≤ 1e18Solution: According Lucas's theorem, since we are considering modulo 2, we can observe that i can …

Yuki 125 悪の花弁

Problem Description: There are K kinds of colors, each with at least one instance of object. There are C[i] number of instances of color i. You are to arrange them into a ring, and you want to know how many different kinds of rings could b…

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 ! * …