Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12045 - Fun with Strings (この記事を編集する[管理者用])

Source

Next generation Contest 6 (2011-06-25)
UVa 12045

問題概要

時間1に,aとbのみからなる文字列があるとする.
それは,時間1経つと,aはbに置き換わり,bはabに置き換わる.
時間Nで長さX,時間Mで長さYであったという情報が与えられた時,時間Kでの長さ mod 1000000007で求める問題.
入力の条件を満たす文字列が存在しないならそれを指摘する.
N, X, M, Y, Kは1以上10^9未満で,XとYは異なる.

解法

最初のaとbの数だけでその後の文字列の長さは決まり,逆に二次連立線形方程式を解けば,最初のaの数,bの数が求まる.
それが非負整数じゃなければ不可能.(自分は誤差が怖いのでmod 1000000007でやって,普通の整数の世界で解が正しいか確かめた)
係数はフィボナッチになるので,ある程度NやMが大きいと,長さ10^9に収まらないので,即座に不可能を返す.
後は,K番目を求めるときに,K番目ぐらいのフィボナッチ数をmod 1000000007で求める必要があり,それは行列べき乗などで求まる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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