ロアちゃんかわいい

競プロっぽい話がなされる駄文の掃きだめ

自作の関数の保存というのをやってみました

おはようございます、すっかり冬休みですね。今日も夢月ロアちゃんが可愛いです。

2週間何してたんだ?(不敵に笑う麻生さんの画像)とかやるのやめてください。何もしていません。
何もしてない割に学生証なくしたりして散々です。自殺~!

前置き長いと某ーたくんとかに嫌味を言われるので、さっさと本題に入ります。

いくつか、関数とかデータ構造を実装したのでここに載せておきます。

本当は関数テンプレートとかなんとかすればもっと便利なのが使えると思うんですが、某cebookの創設者が言っているようにとりあえず完成させました。

今回実装したのは次の3つです。

1.mod付き指数関数

その名の通り、modの範囲で整数のべき乗を求めます。
数学関数だけど、競プロはたまに使うっぽいので保存しておくことにしました。

//関数名:mod_pow
//概要:modつき指数関数
//第一引数a:指数の底
//第二引数b:指数
//第三引数mod:法となる値
//戻り値:a^b(m mod)
long long mod_pow(long long a, long long b, long long mod){
    if(b == 0) return 1;
    if(b % 2 == 0){
        long long d = mod_pow(a,b/2,mod);
        return (d*d)%mod;
    }else return a%mod*mod_pow(a,b-1,mod)%mod;
}

まあ、これは次の関数の為に作ったと言っても過言ではないです。

2.mod付き二項係数

modの範囲で二項係数を求めます。
「普通に二項係数を求めたい!」「long long int型以外も使いたい!」みたいなのは知りません、普通の二項係数なら簡単に実装出来ると思うのでどうぞ。

二項係数を知らない人(中学生がこんなブログを見るか知らんけど)に向けて簡単に説明を書いておきます。

二項係数nCrとは、n個の異なるものからr個を選ぶときの選び方の総数です。数Aでやります。
例えば5個のボールに1から5までの番号が振られているとして、この中からボールを3個選ぶとすると、
(1,2,3),(1,2,4)(1,2,5)
(2,3,4),(2,3,5)
(3,4,5)
の6通りです。しかし全列挙していては手間なので、計算方法が考案されています。
まず、n個のものからr個の物を取り出して並べるような並べ方の総数(これはnPrと表記されます)を求めてみましょう。
上の例で5P3を求めるなら、まず5個のうちから1つ選んで並べ、残った4個から選んで……とやると、
5P3 = 5×4×3 = 60 (通り)
が分かります。同様に、
nPr = n(n-1)(n-2)……(n-r+1)
となります。
さて、nCrというのはn個のものからr個を選ぶときの選び方の総数なので、nPrはこの選び方1つに対し、r!の並び替え方を掛け合わせたものという事が分かります。つまり、
nCr×r! = nPr
という事になります。なので、結局
nCr = n!/{(n-r)!r!}
とすればよいことが分かります。
表し方がいくつかあるので、状況に応じて使い分けるのがいいと思います。詳しくは高校数学の美しい物語とか見てみるといいかもしれません。

さて、この実装は階乗の計算か、掛け算と割り算を交互にやっていけばいけそうです。(もちろんオーバーフローに気を付ける必要はありますが)
しかしmodの範囲ではそうはいきません。何しろ上手く割り算が出来ないので。

ただし、modが素数の場合は別です。フェルマーの小定理(知らん人はググって)から考えると、割り算は出来なくても割り算相当の演算ができます。
次に掛け算をしたら1と合同であるような数、すなわち逆元を求めればよいことになります。
というわけで、aで割る代わりにa^(mod-2)を掛けたらよさそうですね。
これは掛け算なのでmodでも可能ですし、この指数計算は上の関数を利用することで上手く行きます。
(当然使うときは上の関数もコピペしないといけません)

以下実装です。

//関数名:mod_combination
//概要:modつき二項係数
//第一引数n:組み合わせの全体
//第二引数r:何個取り出すか
//第三引数mod:法となる値
//戻り値:nCr(m mod)
long long mod_combination(long long n,long long r,long long mod){
    if(r > n) return 0;
    if(n == r || r == 0) return 1;
    long long fact1 = 1,fact2 = 1;
    for(long long i = n; i >= n-r+1; i--) fact1 = fact1*i%mod;
    for(long long i = r; i >= 1; i--) fact2 = fact2*i%mod;
    return fact1*mod_pow(fact2,mod-2,mod)%mod;
}

3.Union-find

Union-findはグループ分けの為のデータ構造です。
グラフを連結したり、各要素が繋がっているかの判定を行ったり、属しているグループの要素数を求めたりできます。
これらは他のアルゴリズムでも出来なくはないですが、実装が大変だったり時間がかかったりします。

データ構造はこれの他にも二分探索木とか実装してあるんですが、貼る気が起きないのでやめておきます。
以下実装です。

//unionfind
//根にはグループの要素数(負)、それ以外には根の値
//初期値は-1
vector<int> uni(100000,-1);
//引数aの根を求める、なければaを根として返す
int root(int a){
    if(uni[a] < 0) return a;
    return uni[a] = root(uni[a]);  
}
//頂点aとbを繋ぐ
//元々同じグループであればfalse
bool unite(int a, int b){
    a = root(a);
    b = root(b);
    if(a == b) return false;
    if(uni[a] > uni[b]) swap(a,b);
    uni[a] += uni[b];
    uni[b] = a;
    return true;
}
//頂点aとbが同じグループかを調べる
bool isconnected(int a, int b){
    return root(a) == root(b);
}
//頂点aを含むグループの頂点数を調べる
int unisize(int a){
    return -uni[root(a)];
}

以上が最近の成果になります。
あまりめぼしいのがないので、今週は頑張りたいと思います。差し当たっては失くした学生証を見つけようと思います。

ではおやすみなさい。僕は交番に行ってきます。