Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 11964 - Equation (この記事を編集する[管理者用])

Source

Huge Easy Contest II (2011-04-09) (blog)
UVa 11964

問題概要

 x_0 + 2 * x_1 + 4 * x_2 + … + 2^t * x_t = K
の非負整数解の個数をmod Mで求める問題.
tは十分大きいと仮定して,x_0~x_tまでは0以上の整数,K (10^5以下) は与えられる整数.
Mは10^15以下で,150以上の素数を素因数に含まないとする.
テストケースの数は10^5以下.

解法

解の個数はDPで求まるけど,毎回Mが違うのがポイント.
テストケース数が多いので,毎回DPすると間に合わない.
2以上150以下のそれぞれの素数pに対して,p^kが10^15を超える程度にkを選んで,mod p^kで最初にDPしておく.
後は,中華風剰余定理を使って,それぞれのテストケースに対して答えを求める.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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