0w1

Math

Yuki 301 サイコロで確率問題 (1)

Problem Description: You have a dice with 6 faces, mapping to integer in 1..6. You roll the dice, and sum up them along the process. However, you will reset the sum to 0, when the sum has exceeded N. Find the expected number of rolls you h…

Yuki 546 オンリー・ワン

Problem Description: Given N numbers as C[0...N], L, and H, find the number of values in range [L, H] that is multiple of exactly one value in C.Constraints: 1 ≤ N ≤ 10 1 ≤ C[i] ≤ 1e9 1 ≤ L ≤ H ≤ 1e9Solution: Solve for (L' = 1, H' = H) and…

CFR 428 D. Winter is here

Problem Description: You are given an array A[] of N values. For each subset that has gcd greater than 1, its contribution is gcd * size_of_subset. Output the sum of contributions for every such subset, modulo 1e9 + 7.Constraints: 1 ≤ N ≤ …

POJ 1286 Necklace of Beads

Problem Description: Three colors of beads are available. Count the number of different circular necklace that could be formed. Two necklaces are identical iff after some rotation or flip, each position has the same color of bead.Constrain…

POJ 2345 Central heating

Problem Description: There are N switches and N technicians. Each technician has a list of valves, and if he were hired, he would flip the switch of each of them in his list. It is known that for any technician i, it is impossible to repla…

GCJ Japan 2011 Final B. Multiplication of Bacteria

Problem Description: There are T standalone test cases in this problem. In the beginning, there are A units of bacteria. For any moment t with x units of bacteria, we know that moment t + 1 would have x**x units of bacteria. Given A, B, C,…

POJ 2720 Last Digits

Problem Description: f(x) = 1, if x = 0 B ** f(x - 1), otherwise Given B, I, and N, find the last N digits of f(I).Constraints: Solution: We want to find . For any , we can observe that in , we can always find some such that . We will recu…

POJ 2115 C Looooops

Problem Description: You have a for loop that looks like this: for (value_type i = A; i != B; i += C) ; , where value_type is K-bits unsigned integer data type. You want to know whether the loop will reach an end, and if it will, the numbe…

POJ 1150 The Last Non-zero Digit

Problem Description: Given N, M, find the last non-zero digit in N! / (N - M)!.Constraints: 0 ≤ M ≤ N ≤ 2e7Solution: We can find a and k such that in O(lg x) time, given that e is 2 or 5 (because they are prime, we can apply Wilson's theor…

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…

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 は整数である。解法: 首先顯然兩個維度可以獨立看待,因此考慮…