Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 11675 - Happy Friends (この記事を編集する[管理者用])

Source

Regional Warmup 1 (2009-09-13)
UVa 11675

問題概要

ノード数30以下のグラフが与えられる.ノードにスコアが付いている.
初期スコアは,入力で与えられる特定のノードのみ1,その他は0.
時間が1進むと,自分と直接繋がっているノードのスコアの和だけ自分のスコアが増える.
けども,前回の時間で自分のスコアが増えていたら,今回は増えない.
時間t後の全てのノードのスコア mod 1000000007で求める問題.
tは大きい.

解法

行列乗算.ただし,奇数時間と偶数時間で行列が変わる.
ので,ABABABABABABABAとかABABABABとかを求めれば良いことになる.
A(BA)^nか(AB)^nか.
あるノードが奇数時間と偶数時間,どちらで値が増えるかは,最初にスコアが1のノードからの距離を調べればわかる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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