0w1

Math

CFR 776 C. Molly's Chemicals ( Math )

Problem - 776C - Codeforces題意: 給你一個長度 N 的序列,以及 K。問有多少個區間的總和是 K 的非負整數次方。制約: The first line of input contains two integers, n and k, the number of chemicals and the number, such that the total affection …

CFR 662 A. Gambling Nim ( Linear Basis, Math, Probability )

Problem - A - Codeforces題意: 有 N 張卡牌,正面和反面各有一個非負整數。現在兩個人玩遊戲,每場開局每張牌會均勻隨機呈正面向上或背面向上。把 N 個呈現在上的數字當做 N 堆的石頭,進行 Nim 的遊戲。雙方絕頂聰明的前提下,先手贏的機率為何。制約: T…

CFR 806 A. Success Rate ( Math, Extended GCD )

Problem - A - Codeforces題意: 你現在寫了 y 個題目,答對了 x 個。你想知道你最少要再寫幾題才能有答對比率 p / q。若無解輸出 -1。制約: The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases. Each of the next t l…

Monthly Training Farm - May 2017 C. factor1 ( Math, Sqrt Decomposition )

ICPC Blog Online JudgeProblem Description: Given A, B, print number of positive factors of all values between integer in [ A, B ].Constraints: 1 ≤ A ≤ B ≤ 1e14Solution: Consider calculating result of [ 1, B ] - [ 1, A - 1 ]. It uses simila…

Monthly Training Farm - May 2017 B. operator1 ( Math )

https://oj.icpc.tw/contest/5/problem/BProblem Description: Define operator @ with following property: To calculate a @ b, first we transform them into base 3, then apply addition without carry. For example, 7 @ 8 = 21_3 @ 22_3 = 10_3 = 3. …

CFR 622 F. The Sum of the k-th Powers ( Lagrange's Interpolation, Math )

Problem - 622F - Codeforces題意: 令 f( k, x ) = sum( pow( i, k ) for i in range( 1, x + 1 ) ) % ( 1e9 + 7 )。 問 f( K, N ) 是多少。制約: 1 ≤ N ≤ 1e9 0 ≤ K ≤ 1e6解法: 很神奇,還沒看到這題的時候我就有想過手算一樣的問題了,還蠻顯然是用拉格…

CFR 598 C. Nearest vectors ( atan2 )

Problem - 598C - Codeforces題意: 給 N 個非零向量,求任意一對夾角最小的向量對。資料規模: N ≤ 1e5解法: 極角排序。 atan2( y, x ) 回傳的範圍在 [ -pi, pi ] 之間,只有 atan2( 0, 0 ) 是未定義的。時間 / 空間複雜度: O( N lg N ) #include <bits/stdc++.h> using </bits/stdc++.h>…

HE Numbers Summation ( OEIS, Math, Square Root Decomposition )

https://www.hackerearth.com/challenge/competitive/april-circuits-17/algorithm/numbers-summation/題意: 給 N,求 S 對 1e9 + 7 取模。制約: 1 ≤ N ≤ 1e15解法: 無恥怒查 OEIS。 如果想認真解起來,要領應該跟這個是一樣的。時間 / 空間複雜度: O( N…

HE Fredo and Maths ( Math, Totient function )

Fredo and Maths | Totient Function & Math Practice Problems | HackerEarth題意: T 筆詢問。問 x^x^x^x^x^x... % M,其中有 K 個 x,為多少。制約: 1 ≤ T ≤ 1e5 1 ≤ M ≤ 1e7 1 ≤ K ≤ 1e18 M 解法: 利用尤拉定理可以知道,x^phi( M ) % M == 1,利用這…

HE Help Fredo ( Math, Binary Search )

Help Fredo | Binary Search & Algorithms Practice Problems | HackerEarth題意: 給 N 個元素,問最小的 x ,使得 A[ 0 ] * A[ 1 ] * A[ 2 ] .. A[ N - 1 ] 制約: 1 ≤ N ≤ 1e5 1 ≤ A[ i ] ≤ 1e10解法: 經典題,開 log 比較,二分搜 x。時間 / 空間複雜度…

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…

CFR 364 D. Ghd ( Random, Math )

Problem - D - Codeforces題意: 給長度 N 的數列 A。問最大的數,使得該數是數列中一半以上的數的因數為何。制約: N ≤ 1e6 A ≤ 1e12解法: 令答案為 g,那麼有一半以上的數字是 g 的倍數。 因此考慮隨機選取一個下標 r,把所有 gcd( A[ r ], A[ i ] ) 算出…

Yuki 377 背景パターン ( Burnside Lemma, Math )

No.377 背景パターン - yukicoder題意: H * W 格子的壁紙,每個格子有 K 種顏色中一種。這個壁紙由無窮左到無窮右不重疊貼滿,無窮下方至無窮下方也一樣。問牆壁的圖案有多少種,對 1e9 + 7 取模。兩個牆壁的圖案相同若且唯若同時存在相同一個 H * W 的圖案…

HR Colliding Circles ( Math, Expectation )

Programming Problems and Competitions :: HackerRank題意: 有 N 個線段,用長度描述。每一秒以均等機率有兩個線段合併 ( 長度變為總和 )。問期望上 K 秒後,每個線斷所成的圓面積總和為何。制約: 1 ≤ N ≤ 1e5 0 ≤ K ≤ N - 1 0 ≤ R[ i ] ≤ 1e4解法: 首先…

CFR 798 C. Mike and gcd problem ( Math )

Problem - C - Codeforces題意: 給長度為 N 的數列 A。每次可以進行的操作為,選擇一個 i,並執行 A[ i ], A[ i + 1 ] = A[ i ] - A[ i + 1 ], A[ i ] + A[ i + 1 ]。問至少要進行幾次操作,才能使得 gcd( A ) > 1。制約: The first line contains a singl…

CFR 795 G. Perfectionist Arkadiy ( Math )

Problem - G - Codeforces題意: 給 A, H, W,代表有一個紙張 H * W 大小,圖片是一個邊長為 A 的正方形。現在要放任意個正方形,使得所有相鄰正方形之間,以及邊界和其相鄰的正方形的間距為任意實數 x。問 x 最小可以是多少,無解則輸出 -1。制約: The fir…

CFR 795 E. Big Number and Remainder ( Math )

Problem - E - Codeforces題意: 給大數 N,以及一個數字 M。考慮 N 的所有循環 ( N[ x : ] + N[ : x ], for any N[ x ] != 0 ),問其中模 M 後最小的數字為何。制約: The first line contains the integer which Stepan has. The length of Stepan's integ…

GCJ 2017 Qual C. Bathroom Stalls ( Math )

Dashboard - Qualification Round 2017 - Google Code Jam題意: 有 N 個空間排成一排,有 K 個人依序決定自己要進哪個空間。令一個空間 i 的左邊連續空房間的數量為 L[ i ],右邊連續空房間的數量為 R[ i ],那麼任何人都會優先考慮 min( L[ i ], R[ i ] ) …

ARC 071 D - 井井井 ( Math )

D: 井井井 / ### - AtCoder Regular Contest 071 | AtCoder題意: 在二維座標系上,給 N 個縱線,M 個橫線,問所有可形成的四邊形面積總和。輸出答案對 1e9 + 7 取模。制約: 2≤n,m≤1e5 xi,yi は整数である。解法: 首先顯然兩個維度可以獨立看待,因此考慮…

CFR 616 E. Sum of Remainders ( Math, Sqrt Decomposition )

Problem - E - Codeforces題意: 給 N, M,求: 資料規模: The only line contains two integers n, m (1 ≤ n, m ≤ 1e13) — the parameters of the sum.解法: 首先觀察到 因此所求可以寫成 考慮比較簡單的這個問題: 這個的求法是基於平方分割,細節和這篇…

PE 401 Sum of squares of divisors ( Math, Sqrt Decomposition )

Well, I know that posting this might no be completely appropriate but...題意: 問 [ 1, 1e15 ] 所有整數的因數平方總和為多少。解法: 也就是平方分割,而枚舉 d 轉換成枚舉 N // d 那部分我一直很搞不清楚,但其實只要知道這件事就可以理解: 這件事成…

CFR 327 C. Magic Five ( Math )

Problem - 327C - Codeforces題意: 給一個大數 A,將其複製 K 次連接成一個新的大數 S。問有多少種方法任意刪除 S 中的數字,使得留下來的數字被 5 整除。允許領導 0,但不允許空字串。兩個方法相同若且唯若兩個方法刪除的數字的位置都是一樣的。資料規模:…

CFR 86 D. Powerful array ( Mo's Algorithm, Math )

Problem - D - Codeforces題意: 給一個長度為 N 的數列 A[]。T 筆詢問,問對 [ L, R ] 中存在的所有相異數值 s,SUM( K[ s ] * K[ s ] * s ) 是多少。K[ s ] 代表 [ L, R ] 區間中,s 出現的次數。資料規模: First line contains two integers n and t (1 …

CFR 656 B. Scrambled ( Math, Periodic, Python )

Problem - B - Codeforces題意: 這是愚人節題,瓶頸貌似是在要花點時間把這稍微被打亂的文章看完。 總之題意就是給 M, R,問 [ 0, ∞ ] 這些整數中,有多少百分比的 d 對任意一個 0 ≤ i 資料規模: N, MAXM, MAXR ≤ 16解法: 顯然會以 LCM 為單位形成週期。…

AGC 12 D - Colorful Balls ( Math, Combination )

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

CFR 788 C. The Great Mixing ( Math, bitset, DP )

Problem - C - Codeforces題意: 你的目標濃度是 N / 1000。你有 K 種液體,濃度分別為 a[ i ] / 1000。每一種液體可以用任意非負整數單位容量,求最小正整數,代表使用的總容量成功調配出目標濃度。資料規模: The first line contains two integers n, k (…

CFR 792 E. Colored Balls ( Math, Sqrt Decomposition )

Problem - E - Codeforces題意: 給 N 種球的個數 A[]。要求按照下列規則將其分箱: 1. 同一個箱子不能存在兩種球 2. 最多球的箱子的球數和最少球的箱子的球數之差不得超過 1 3. 所有球都必須存在於一個箱子裡 4. 不得有空箱 問最佳的分箱方式下,可以用最少…

CFR 786 C. Till I Collapse ( Math, Sqrt Dcmp, Divide and Conquer )

Problem - C - Codeforces題意: 給一個長度為 N 的陣列,用顏色描述。要求對於所有 K 資料規模: N ≤ 1e5解法: 據說這可以用資料結構 ( 樹狀數組 ) 直接做掉,但我看不懂。 首先答案一定是非嚴格遞減的。 這題的重點在於看透一個結論:「答案的種類大約在 …

POI 2 Stage 3 Job Scheduling ( Greedy, Math )

http://main.edu.pl/en/archive/oi/2/sze題意: 有 N 個工作,假設當前時間已經過 T 單位,那麼工作 i 需要花費的時間為 A[ i ] * T + B[ i ]。一次只能做一個工作,問最短時間完成的工作序列。資料規模: In the first line of the standard input there is…

POI 2 Stage 2 Triangles ( Ad hoc, Math, Fibonacci )

http://main.edu.pl/en/archive/oi/2/tro題意: 給很多邊的長度,問是否可以構成三角形,可以的話輸出方案。資料規模: In the standard input there is a finite sequence of at least three positive integers not greater then 1e9, terminated by the nu…