スポンサーサイト

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

Codeforces Round #167 (Div. 1) B : Dima and Two Sequences

整数のペアが 2n 個あり、
(a_1, 1), (a_2, 2), ..., (a_n, n),
(b_1, 1), (b_2, 2), ..., (b_n, n)
という形をしている。
これらを第一成分が非減少になるように並べかえる方法は何通りあるか?
mod m で求めよ。

・ 1 ≦ n ≦ 10^5
・ 1 ≦ a_i, b_i ≦ 10^9
・ 2 ≦ m ≦ 10^9+7

解答

c_1 個の 1、c_2 個の 2、...、c_n 個の n を一列に並べる方法の数が
(c_1 + c_2 + ... + c_n)! / (c_1!・c_2!・...・c_n!)
となることを使えば、答えは
c! / (2!・2!・...・2!)
みたいな値の積になる。
m が 2 の倍数かもしれないので 2 の逆元がないかもしれない。
分子で mod をとる前に先に訳文を済ませておけばいい。

ソースコード

http://www.codeforces.com/contest/273/submission/3115724
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。