積の和典型 - Shirotsume の日記
最近積の和典型が話題になっているので書きます。 N個のマス目が横一列に並んでいる状況を考えます。初め、全部のマスは白色です。このうち K 個のマスを選んで黒く塗った時にできるマスの状態は何通りでしょうか？ これを こうする これは 通りです。 これを応用すると、次のような問題が解けます。 長さが N であって、総和が M である非負整数列の個数を求めよ。 非負整数列というのは、各要素が負の数でない整数からなる数列です。[1, 2, 3, 4, 5] とか [0, 0, 1, 4, 3] とかです。これの個数を数えるのに、先ほどのマスの数え方を使うことができます。 まず、 M + N - 1 個の白いマス目を用意します。そのあと、そこから N - 1 マス選んで塗ります。こうしたとき、必ず M 個のマスが白いままで残っています。また、マスの両端や黒マスを境目として考えると、白いマスが連続する
拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜 - Qiita
NTT データ数理システムでアルゴリズムの探求をしている大槻 (通称、けんちょん) です。好きなアルゴリズムは二部マッチングです。今回は、歴史の記録に残る最古のアルゴリズムの 1 つとして知られるユークリッドの互除法について書きます。 ユークリッドの互除法は、最大公約数を求めたり、一次不定方程式 $ax + by = c$ に応用したりなど、大学受験でもお馴染みのアルゴリズムですが、整数論的アルゴリズムや数え上げアルゴリズムにおいて根幹を成す重要なものでもあります。 今回の記事では特に、一次不定方程式 $ax + by = c$ の整数解を一般に求めるアルゴリズムとして知られる「拡張ユークリッドの互除法」の理解を目指します。 1. ユークリッドの互除法とは ユークリッドの互除法は、2 つの整数 $a$, $b$ の最大公約数を効率よく求めるアルゴリズムです。本記事では $a$ と $b$
楕円同士の接触判定と衝突判定
ググっても出てこなかったので。 2つの楕円が接している（内接 or 外接）かどうか判定する方法についてです。ついでに衝突判定もできます。 衝突判定だけしたい方 以下で説明する方法でも判定自体はできますが、非常に非効率です。悪いことは言いません。GJK法などを使いましょう。凸同士なので簡単にできます。 どうしても接触を判定したい方 心して読み進めてください。 事の発端 まだそんなにバズってないけど宣伝していいらしいので． AI でも普通のプログラマーでもない優秀なプログラマーたる皆さんは，もちろん楕円が接するか判定する方法を知っていますよね？ 私は一昨日実装しました．各位の解法に興味があります．よろしくお願いいたします． — 青い楕円形のぜろ (@0_uda) October 4, 2022 もちろん楕円が接するか判定する方法を知っているので、書くことにしました。 楕円の表現方法 楕円とはい
「998244353 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita
1. なぜ 998244353 で割るのか？ 最初はこのような設問を見るとぎょっとしてしまいますが、実はとても自然な問題設定です。 $998244353$ で割らないと、答えの桁数がとてつもなく大きくなってしまうことがあります。このとき以下のような問題が生じます: 多倍長整数がサポートされている言語とされていない言語とで有利不利が生じる 10000 桁にも及ぶような巨大な整数を扱うとなると計算時間が膨大にかかってしまう 1 番目の事情はプログラミングコンテストに特有のものと思えなくもないですが、2 番目の事情は切実です。整数の足し算や掛け算などを実施するとき、桁数があまりにも大きくなると桁数に応じた計算時間がかかってしまいます。実用的にもそのような巨大な整数を扱うときは、いくつかの素数で割ったあまりを計算しておいて、最後に中国剰余定理を適用して復元することも多いです。 なぜ 9982443
『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！ - YouTube
「フカシギの数え方」おねえさんといっしょ！みんなで数えてみよう！ ※LINEスタンプ「フカシギお姉さんと仲間たち」をリリースしました。※ "The Art of 10^64 -Understanding Vastness-" Time with class! Let's count! LINE sticker "Combinatorial Explosion!" has been launched! http://line.me/S/sticker/1143771 「フカシギの数え方」で紹介している、組み合わせ爆発の例です。 「それでもね。私はみんなに「組み合わせ爆発のすごさ」を教えたいの！止めないで！」 お姉さんと子どもたちが実際に数え上げる大変さを伝えます。 This is an example about combinatorial explosion. "I want to de
二項係数 mod 素数を高速に計算する方法 [累積和, フェルマーの小定理, 繰り返し二乗法, コンビネーション, 10^9+7] - はまやんはまやんはまやん
要望 nCk mod 10^9+7を高速に計算したい n,k≦10^5 追記：llはlong longのことです 使ってるテンプレートはこんな感じです。 #include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<b;i++) using namespace std; typedef long long ll; 高校で習うやり方でやると… ll mod = 1000000007; //--------------------------------------------------------------------------------------------------- ll C(int n, int k) { ll res = 1; rep(i, 0, k) res = (res * (n - i)) % mod; rep(
![二項係数 mod 素数を高速に計算する方法 [累積和, フェルマーの小定理, 繰り返し二乗法, コンビネーション, 10^9+7] - はまやんはまやんはまやん](https://cdn-ak-scissors.b.st-hatena.com/image/square/e5b388d4aa8524d7a1ac008f05bde9a2dccdd7a8/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F10328537792368951407%2F17391345971651666693%2F1582545411)
N番目の素数を求める - すぎゃーんメモ
SNSなどで話題になっていたので調べてみたら勉強になったのでメモ。 環境 Pythonでの実装例 例1 例2 例3 エラトステネスの篩 Rustでの実装例 試し割り法 エラトステネスの篩 アトキンの篩 おまけ: GMP Benchmark 高速化のテクニック 上限個数を見積もる Wheel factorization オチ Repository References 環境 手元のMacBook Pro 13-inchの開発機で実験した。 2.8 GHz Intel Core i7 16 GB 2133 MHz LPDDR3 Pythonでの実装例 例1 最も単純に「2以上p未満のすべての数で割ってみて余りが0にならなかったら素数」とする、brute force 的なアプローチ。 import cProfile import io import pstats import sys def m
よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方 - けんちょんの競プロ精進記録
1. 典型的な二項係数の求め方 競プロをしていると、「 mod 」を計算する場面にしばしば出くわします。最近では、 であることが多いですね。 mod の計算方法は、時と場合によって色んな方法が考えられますが、すぐ下で紹介する方法が最も頻繁に使用されています。多くの AtCoder のトッププレイヤーたちも使用している形式で、高速です。 使い方としては、最初に一度前処理として COMinit() を呼び出します。その後は、毎回 COM(n, k) 関数を呼べばよいです。 前処理 COMinit()：計算量 クエリ処理 COM(n, k)：計算量 1-1. mod の実装 この実装では、ACL (AtCoder Library) の modint を用いています。さらに下に、modint を使わない実装も載せています。 #include <iostream> using namespace s
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
