ルーカスの定理による巨大な組み合わせ数の剰余計算
整数 \(n, m\) と素数 \(p\) に対して、以下の関係が成り立つ：
\[ \binom{n}{m} \bmod p = \binom{n \bmod p}{m \bmod p} \cdot \binom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \bmod p \]
この定理は、\(n\) や \(m\) が非常に大きく、通常の逆元計算（フェルマーの小定理など）が使えない場合に特に有効である。たとえば、\(m\) が \(p\) の倍数だと逆元が存在せず ...
8月19日 04:23 投稿
等比数列の効率的計算と木構造処理
T1: 等比数列の合計計算
数列$ \sum_{i=1}^n x^i $を効率的に求めます。この問題ではx進法の特性を利用した新しいアプローチを採用しました。
変数Pを$x^1 + x^2 + ... + x^n$と定義すると、x進法で表現する際は連続する1の並びになります。この性質を活かし、$Q = x^{m+1}$のx進法表現から$Q-1$を導出し、$(x-1)$で割ることで最終的な合計値を得ます。
以下に数式を示し ...
8月15日 17:07 投稿
アルゴリズム解説：組合せ数学、基環木DP、および数論篩の実装
問題1：グリッド経路の組み合わせと寄与計算
本問はグリッド上の経路数と各初期値が最終結果に与える寄与度を計算する問題です。始点から終点 $(N, M)$ への移動において、右と上のみ移動可能と仮定します。各地点 $(i, j)$ から $(N, M)$ への移動経路の総数は、右への移動回数と上への移動回数の組み合わせにより $\frac{(N-i + M-j)!}{(N-i)! (M-j)!}$ で求められます。 ...
8月11日 17:39 投稿
第二種スタirling数の学習メモ
1. 定義
第二種スタirling数 \(S(n, k)\)（または \(\genfrac{\{}{\}}{0pt}{}{n}{k}\) と表記）は、\(n\) 個のラベル付きの要素を \(k\) 個のラベルなしの空でない部分集合に分割する方法の数を表します。
組み合わせ論的意味から、\(n < k\) のとき \(\genfrac{\{}{\}}{0pt}{}{n}{k} = 0\)、\(n = k\) のとき \(\genfrac{\{}{\}}{0pt}{}{n}{k} = 1\)、\(k = 0\) のとき \ ...
7月25日 16:16 投稿
Codeforces Edu Contest 161 解法と分析
問題A: 文字列照合判定
この問題では、文字列cの各文字が対応する位置の文字列aまたは文字列bのいずれかと一致するかを判定する必要があります。すべての文字が一致する場合は"NO"、そうでない場合は"YES"を出力します。
#include
#include
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int test_cases ...
7月7日 20:03 投稿