Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1203-c1ded044
この記事にトラックバックする(FC2ブログユーザー)

PKU 3761 - Bubble Sort (この記事を編集する[管理者用])

Source

PKU Campus 2010 (POJ Monthly Contest 2010.05.09) (参加記録)
PKU 3761

問題概要

1~Nのpermutationのうち,バブルソートでK roundでソートが完了する物の数をmod 20100713で求める問題.
Nは1000000以下.

解法

適当なNについて,全探索で答え求めてみると規則に気づく.
それの証明方法は,例えば,最初場所iにいたものが左の数字に「抜かれる」回数を考えてみる.
一度でも抜かれないと,次回以降のRoundでは抜かれない.
抜かれる回数は,自分より左にいた,自分より大きな数字の数.
抜かれる回数の最大値は,それぞれ,位置iにいた数字はi-1回まで.
Round数は,抜かれる回数の最大値に等しい.
などを考える.
階乗の値は,最初に1000000!まで求めておく.べき乗はlog nで行う.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1203-c1ded044
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。