zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC159-A「The Number of Even Pairs」です。
ポイント
簡単な組み合わせ演算の問題です。${}_{N} C_{2} + {}_{M} C_{2}$を計算すれば良いので，簡単には以下の式で解答することができます。
\begin{align}
{}_{N} C_{2} + {}_{M} C_{2} &= \frac{1}{2}N(N-1) + \frac{1}{2}M(M-1)
\end{align}
{}_{N} C_{2} + {}_{M} C_{2} &= \frac{1}{2}N(N-1) + \frac{1}{2}M(M-1)
\end{align}
しかし，勉強のために今回は一般の二項係数の関数を作り，そこで${}_{N} C_{2} + {}_{M} C_{2}$を計算してみましょう。二項係数の計算に関しては，以下の記事をご覧ください。
あわせて読みたい
【c++で楽しく実装！】二項係数（コンビネーション）の計算
本記事では，二項係数の簡単な解説と実装例をお伝えしていきます。使用言語はc++です。その他の競技プログラミング関連の記事は，以下の目次をご覧ください。 目次へジ...
おさえるべき内容
二項係数の計算方法
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;
// 考える整数の最大値
const int MAX = 200;
// 今回採用する大きい素数を適当に設定
const int MOD = 1000000007;
// メモを保管する場所
ll fact[MAX], inv_fact[MAX], inv[MAX];
// メモを計算する
void init() {
// 初期値設定と1はじまりインデックスに直す
fact[0] = 1;
fact[1] = 1;
inv[0] = 1;
inv[1] = 1;
inv_fact[0] = 1;
inv_fact[1] = 1;
// メモの計算
repi(i, 2, MAX){
// 階乗
fact[i] = fact[i - 1] * i % MOD;
// 逆元
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
// 逆元の階乗
inv_fact[i] = inv_fact[i - 1] * inv[i] % MOD;
}
}
// 二項係数の実体
ll nCk(int n, int k) {
ll x = fact[n]; // n!の計算
ll y = inv_fact[n-k]; // (n-k)!の計算
ll z = inv_fact[k]; // k!の計算
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return x * ((y * z) % MOD) % MOD;
}
int main(){
init();
int N, M;
cin >> N >> M;
cout << nCk(N, 2) + nCk(M, 2) << endl;
}
コメント