Math
No.320 眠れない夜に - yukicoderかなりフィボナッチ数列の勉強になったので、ちょっとノートをします。pekempey さんの記事を参考にしました。ある項目に 1 少なく数えるのは、その項目から と負のフィボナッチ数列を並列して進ませる事と同じで、縦の総和…
No.389 ロジックパズルの組み合わせ - yukicoder題意： 在一排 M 個格子上放黑色點，依序為 H[ 0 ], H[ 1 ] .. H[ N ] 個連續的黑色點，且兩兩以至少一個的連續白色點區隔。求模 1e9 + 7 後的方案數。資料規模： 1 ≤ M 0 ≤ H[ i ] SIGMA{ H } ≤ M 保證若有一…
No.403 2^2^2 - yukicoder自分が pow() の中に普段書いてる res = 1 は間違ってるみたですね。0^n = 0, for all n > 0 ですから。 const int MOD7 = ( int ) 1e9 + 7; ll A, B, C; void init(){ scanf( "%lld^%lld^%lld", &A, &B, &C ); } ll ll_pow( ll v, …
No.152 貯金箱の消失 - yukicoder 直角三角形の辺はそれぞれ x * x + y * y, x * x - y * y, 2 * x * y と表せる。 総和をとると、2 * x * x + 2 * x * y ≤ L が問題の核心だと分かる。 ここで x, y を枚挙。 #include <bits/stdc++.h> using namespace std; signed main(){</bits/stdc++.h>…
No.176 2種類の切手 - yukicoder先に T ≥ lcm( A, B ) させるように余る lcm( A, B ) * k を最大の整数 k で取る。 すると最悪の場合、T = 1e9, max( A, B ) = min( A, B ) = 1e4.5 となる。 しかしここで max( A, B ) を枚挙しても間に合う。 O( sqrt( T ) …
No.53 悪の漸化式 - yukicoder 高校数学は忘れないでおきましょう yukicoder No.53 - 悪の漸化式（writer担当） - ゲームにっき（仮）別館（仮） #include <bits/stdc++.h> using namespace std; signed main(){ int N; cin >> N; cout << fixed << setprecision( 10 ) << 4</bits/stdc++.h>…
Problem - A - Codeforces題意： 一個方陣，初始所有值為 0，塞 1 進去，1 彼此不相鄰，且最後方陣必須上下、左右分別成對稱。給 1 的數量，求至少要邊長多少的方陣才能塞下。資料規模： 1 的個數 1 ≤ X ≤ 100解法： 先注意到因為必須對稱，奇數邊長的方陣一…
Problem - 566F - Codeforces題意： 給一個嚴格遞增序列。求子序列最長長度，子序列滿足所有相鄰元素對，後一個元素可以被前一個整除。資料規模： 序列長度 1 ≤ N ≤ 1e6 元素大小 1 ≤ A[ i ] ≤ 1e6 時限 1000 ms 記憶體 256 MB解法： 注意到 [ 1, N ] 的數的…
Problem - B - Codeforces 題意： 給一個序列 A，要你求一個相同長度的 B 序列，使 B 序列中任意兩個數字皆互質，此前提下 SIGMA{ abs( A[ i ] - B[ i ] ) } 最小。輸出 B 的長相。 解法： A 最大只會有 30，可以證明 B 只需考慮 [ 1, 60 ] 內的數。因為如果…
https://www.hackerrank.com/challenges/find-the-seed F( n ) = c( 1 ) * F( n - 1 ) + c( 2 ) * F( n - 2 ) .. + c( n ) * F( 0 ) => c( n ) * F( 0 ) = F( n ) - c( 1 ) * F( n - 1 ) - c( 2 ) * F( n - 2 ) .. - c( n - 1 ) * F( 1 ) => F( 0 ) = invers…
https://www.hackerearth.com/april-circuits/algorithm/circ-bear-and-vectors/ Two vectors v1( a1, b1 ), v2( a2, b2 ) are perpendicular to each other iff ( v1 dot v2 ) = a1 * a2 + b1 * b2 = 0. And since ( ka, kb ) = k( a, b ) is parallel to (…
https://www.hackerearth.com/april-circuits/algorithm/2a-bear-and-all-permutations-1/ We can simply simulate for each answer since n is only up to 12. However, it still takes a lot of time, and the number is extremely large, we will have to…
https://www.hackerearth.com/april-circuits/algorithm/circ-bear-and-vowels-2/ Simply simulate as the description provides. #include <bits/stdc++.h> using namespace std; const int MAXS = 50 + 2; const string vowel = "aeiouy"; string s; void solve(){ int vo</bits/stdc++.h>…
Problem - D - Codeforces 2 elements with same value should never co-exist since it will be an even number, which will not be a prime number when summed, unless they were both 1. 2 even numbers nor 2 odd numbers can not co-exist as well. So…
Test Online Judge 這題各種限制很緊，差點以為這個解法行不通 ( 或許我的解法也不是正解 )。 想著應該是要用篩法先預處理，利用質因數分解後的指數做組合算出答案。但如果傻傻地做，就會MLE，所以只能用 short存答案。這樣不會爆是很顯然的，因為最多只會有…
Problem - A - Codeforces f( x ) = k * x + b f^n( 1 ) ≤ f^a( t ) となるような最小な aを求める。 始めは matrix fast power で二分探査しようと頑張ってみたがオーバーフローが出るみたいで失敗した。 ちゃんと考えると、単調増加関数なので両方に f^( -…
http://main.edu.pl/en/archive/oi/19/rozIDDFSで頑張ろうとしたが、当たり前にもTLEした。 24 / 100。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MAXK = 4e17 + 4; int maxd; vector< ll > fib; bool dfs(ll k, int d){ if( k == 0 )</bits/stdc++.h>…
http://codeforces.com/contest/546/problem/D 用質數預處理的方法快速計算每個值可以分解成多少質因數。 #include <bits/stdc++.h> using namespace std; const int MAXT = 1e6 + 6; const int MAXAB = 5e6 + 6; typedef long long ll; ll ps[ MAXAB ]; int val[ MAXAB ], </bits/stdc++.h>…
Fast fourier transform can be applied on multiplication of polynomial functions, giving O( N lgN ) time complexity. One of the most common usage is for fast multiplication on big numbers. It exploits the property of the complex roots of un…
