0w1

Inclusion Exclusion

CFR 803 F. Coprime Subsequences ( Inclusion Exclusion, Math, Sieve )

Problem - F - Codeforces題意: 給 N 個元素的數列 A。問有幾種不同的非空子序列,其最大公因數不為 1。輸出方案數對 1e9 + 7 取模。制約: The first line contains one integer number n (1 ≤ n ≤ 100000). The second line contains n integer numbers a…

Yuki 243 出席番号(2) ( DP, Inclusion Exclusion )

No.243 出席番号(2) - yukicoder題意: 有 N 位可分別的學生,現在你要分配 0 ~ N - 1 的座位給他們。每個學生都有一個不喜歡的座位編號。求每個人都不作到不喜歡的座位編號的方案數,對 1e9 + 7 取模。資料規模: 生徒の数Nが最初の行で与えられる。1≤N≤500…

CFR 372 B. Counting Rectangles is Fun ( DP, Inclusion Exclusion )

Problem - B - Codeforces題意: 給一個 0 / 1 矩陣,Q 筆詢問,求以 ( A, B ) 為左上角,( C, D ) 為右下角的矩陣中,有多少不同的矩形元素全為 0。資料規模: There are three integers in the first line: n, m and q (1 ≤ n, m ≤ 40, 1 ≤ q ≤ 3e5). Each…

CFR 245 H. Queries for Number of Palindromes ( DP, Inclusion Exclusion, Palindrome, IO = = )

Problem - 245H - Codeforces題意: 給一個字串。接著 Q 筆詢問給左界右界,求對應的子字串中有多少回文子字串。資料規模: 字串長度 1 ≤ | S | ≤ 5000 1 ≤ Q ≤ 1e6 時間限制:2500 ms 空間限制:256 MB解法: 先用 O( N ^ 2 ) 預處理 is_pal[ l ][ r ],表…

CFR 251 E. Devu and Birthday Celebration ( Inclusion Exclusion, Number Theory )

Problem - E - Codeforces題意: Q 筆詢問: 有 N 顆糖果要分給 F 個人,每個人至少拿到一顆,但希望每個人的糖果個數的最大公因數為 1。求方法數模上 1e9 + 7。資料規模: 1 ≤ Q ≤ 1e5 1 ≤ F ≤ N ≤ 1e5 時間限制: 5000 ms 空間限制: 256 MB解法: 考慮 N …