Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

数学

Codeforces 258D - Little Elephants and Broken Sorting

問題文 : Little Elephants and Broken Sorting解法 :dp[i][j] : 場所i, j の数をA[i], A[j] として, A[i] > A[j] となる確率, とすると,この配列の初期値はA[i] > A[j] なら 1, A[i] k 回目において,1 / 2 の確率でa[k] 番めの数とb[k] 番目の数が交換され…

Codeforces 226E - More Queries to Array...

問題文 : More Queries to Array問題概要: 配列 $ \normalsize a$ が与えられるので, 区間 $ \normalsize [l,\ r] $ の値を $ \normalsize x$ に変更する. $ \normalsize \displaystyle \sum_{i = l}^{r} a_{i} \cdot (i - l + 1)^k$ (ただし $\normalsize 0…

IOI 2005-day1 Mean Sequence

問題文 : 平均数列解法 : 数列の初項を決めると, 残りの数列の値も一意に定まる. 更に, 初項k の平均数列が作れなければ, 初項をk + 1 とする平均数列(またはk - 1 とする平均数列, あるいは両方) が作れないことが分かる. ゆえに, この数列の初項の値は連続…

JOI春合宿 2007-day4 lines

問題文 : 直線解法 :オイラーの多面体定理です."V(頂点数) - E(辺数) + F(面数) = D(次元) - 1"が成立するので, D=2から, F = E + 1 - V が求まります. EだったりV だったりは入力から簡単にもとまるので, 愚直に計算しても O(N^2 log N) で解を得ることが出…

準急さんの問題

問題:k<=100, N<=10^18, M<=1,000,000,007のとき、1^k+2^k+…+N^k mod M を1秒で求めるプログラムを作成せよ— 編集の都合上省略さん (@semiexp) 12月 19, 2011昔semiexpさんがこんな問題をつぶやいていたので、解いてみました. 結論から言うと, 僕の環境だ…

ファレイ数列のいろいろ

JOI春合宿や各種コンテスト, JJMOでたまに出題されるファレイ数列についていろいろ書きます. 面白い性質がたくさんあります.・ファレイ数列とは? 約分された分数を昇順に並べた一群の数列であり、正の整数 n に対して、n に対応する (または、属する、深さn…

JOI春合宿 2007-day3 Anagram

問題文 アナグラム(pdf注意, 1枚目)解法 : 元の文字列sの各文字を昇順にソートしたs'を考える. 目的の文字列の前にある順列の総数は, s'の先頭から文字を選んでいき, 元の文字列の接頭辞にならない文字列の組み合わせを全て求めれば求まる. もとの文字列と現…

JOI春合宿 2011-day2 keycards

問題文 : カードキー解法 : 包除原理のようなものをつかう.この問題は, "0 ~ 2 ^ (N - K)までの数から, すくなくとも1つ数をつかって論理積を0にする組み合わせの総数はいくつか", という問題に置き換えられる.数の選び方は, U = 2 ^ (2 ^ (N - K)) - 1 通り…