数え上げ

No.727 仲介人moko - yukicoder

解は Π_{0<=i

E2. Median on Segments (General Case Edition) | Codeforces Round #496 (Div. 3)

f(x) を「中央値をxとする部分文字列の数」とする。f(m)が解。 とおくと を得る。 あとは、g(y)を求めるだけ。g(y)の値は、中央値がy以上の部分文字列の数を表す。 部分文字列の中央値がy以上である必要十分条件は (y以上の値の数)>=(y未満の値の数) とわか…

AOJ 2333 : 僕の友達は小さい My friends are small (JAG Summer 2010)

まずは簡単な例外的な組合せから数えてみる。以下、解をanswerと表記する。どの友達もリュックに入れることができないならばanswer+=1。また、すべての友達をリュックに入れることができるならばanswer+=1。 それ以外の場合を数える。とりあえずリュックに入…

B: Find Symmetries | AtCoder Grand Contest 023

よい盤面である条件は、1<=i<=Nについてi行目とi列目が等しいことと同値。例えばN=4については、以下が等しければよい。 更にこの図から、任意の自然数の組(A, B)について(A+x, B+x) (xは自然数) も(A,B)と比較対象が同じであることがわかる。たとえば、(A, …

E. Max History | Educational Codeforces #38

すべての順列を見ていくのは明らかに無理なので、a[j]ごとに計算していく。つまり、f[a] = f[a] + a[M(もとの配列の添字はj)] となるような順列を数える。その数えをg(j)としておく。g(j)さえ求まれば解はΣa[j]g(j) a[j]より大きい値の数えをx, a[j]以上値の…

yukicoder #563 : 超高速一人かるた large

解説付き const int MO = (int)1e9 + 7; string S[2001]; RollingHash rh[2001]; int f[2001][2001]; mint ans[2001], fact[2001]; int main(){ ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; rep(i, N) { cin >> S[i]; } // 接頭辞の問題=>…

yukicoder #562: 超高速一人かるた small

p(T)を 読み上げられたカードの集合がTであるときのパターン数とする。 p(Φ) = 1 p(T(!=Φ)) = Σ[i ∊ T] ( p(T-{i}) ) で簡単に求まる。 e(T)を読み上げられたカードの集合がTであるときの 期待値 と パターン数の積とする。 E[K] * P[N,K] = Σ[T⊆読み札, |T|…

Counting Perfect Subsequences | HourRank 20

sに含まれる文字xの数をn(x)とする。c, dが無いものと見做してsがa, bだけから成り立つと考えてみよう。f[i]を文字a, bをちょうどi個ずつ含む部分列の数とする。i>min(n(a), n(b))のときaまたはbの数が足りないからf[i] = 0i<=min(n(a), n(b))のときn(a)個の…

yukicoder #503: 配列コレクション

操作回数をa, 最後に残る要素の数をbとする。N>=Kよりa>=1K>=2よりb>=1 最終的にAの各要素はDの累乗になることがわかる。D=1のとき、コーナーケースでAのすべての要素は1になるので解はb 以下、D≠1とする。Aの要素はDの累乗であり、かつ操作回数がaなので、…

SRM 708 DIV1 Medium: PalindromicSubseq

X[i]の値を具体的に求めていこう。 各文字S[i]についてそれぞれX[i]を求める。S[i]がある回文に含まれる場合、S[i]と一致するようなもじS[j]がある。ただし、i=jでS[i=j]が奇数長回文の中心である場合も含む。iとjを総当りで固定した場合、それだけでO(N^2)…