●「先輩！ 第2種スターリング数の勉強をしますよ！」
■「え、何、どうしたの突然」
●「この間のARCのE問題ですよ！ あー悔しい！」
■「あー、数え上げ問題だっけ。あんまり時間残ってなかったし、難しそうだったから早々に諦めちゃったよ」
●「じゃあ一緒に考えましょう！」
■「今日はテンション高いねー」
●「『Everything on It』 ラーメンを注文する問題ですね」
■「どれどれ…… トッピングが N 種類あって、1杯のラーメンには、それぞれのトッピングを選んで乗せられるんだね」
●「1杯のラーメンに同じトッピングを2つ以上乗せるのはダメですね」
■「それで、何杯かラーメンを注文して、全トッピングを2回以上食べたいんだね」
●「2回以上っていうのが厄介ですよね」
■「トッピングの組み合わせが同じラーメンを重複して注文しちゃだめだから、最低でも3杯は必要か」
●「”全部乗せ” と “1つだけ除外したもの” と “除外した1つ” の3種類ですね。”全部乗せ” を2杯頼むのはルール違反ですね」
■「だから N ≧ 2 なんだね」
●「それで、目的を達成するラーメンの組み合わせの数を計算するんですね」
■「なるほど。難しそうな問題だね」
■「パッと思いつくのは、”全種類2回以上食べる方法” よりも “1種類以上が1回以下しか食べられない方法” を数えるのがやりやすそうというイメージかな」
●「”2回以上” だとたくさんパターンがありますけど、”1回以下” なら 0 か 1 ですもんね」
■「でもそれだと “1種類以上が” というのが難しそうだね。”1種類がNG”、”2種類がNG”、…… を足していくことになるのかな」
●「”NG” というのは、1回か0回しか食べられないということですね。でもその方針で考えてみたんですけど、どうもうまくいかなかったんですよね……」
■「そうなんだ。じゃあどうすればいいんだろう」
●「どうやら包除原理を使うみたいですよ」
■「包除原理って、ベン図のあれ？ 場合の数と確率でよく出てくる」
●「はい！ でも、競プロで包除原理を使ったことってほとんど無かったんですよね」
■「僕も無いね。でも包除原理自体は分かるよ」
●「集合Aの要素数を#(A)と書くとき、
#(A∪B) = #(A) + #(B) – #(A∩B)
が成り立つ、というのが基本ですね」
■「3つの集合の和集合でも、
#(A∪B∪C) = #(A) + #(B) + #(C) – #(A∩B) – #(B∩C) – #(C∩A) + #(A∩B∩C)
が成り立つね」
●「一般化するとこんな感じですね」
$$\#\left (\bigcup_{i=1}^nA_i \right )=\sum_{i=1}^n(-1)^{i-1}\sum_{{}_n C_i 通り}\#\left (i個選んだ積集合 \right )$$
■「(-1)^(i-1)は、足すのと引くのが交互になってることを表しているんだね。最初は i=1 だから、(-1)^0 で、足すことになるんだね。Σが2個あってややこしいけど、n=3 の例で考えると、こんな感じか」
#(A∪B∪C) = {#(A) + #(B) + #(C)} – {#(A∩B) + #(B∩C) + #(C∩A)} + #(A∩B∩C)
●「そうですね！ 最初の3つが i=1、次の3つが i=2、最後の3つが i=3 に対応しているんですね。符号も、足す・引く・足す、ですね！」
■「今回の場合は、どうなるんだろう？」
●「知りたい余事象は、”1種類以上のトッピングがNG” なので、”トッピング1がNG または トッピング2がNG または……” となりますよね」
■「じゃあ、
“トッピング1がNG” + “トッピング2がNG” + …… – “トッピング1と2がNG” – ……
という雰囲気かな」
●「そうですね！ このとき、”トッピング1がNG” では、トッピング1以外がOKかNGかはどうでもいいというのがポイントですね」
■「なるほど、包除原理を使うと、そう考えられるから楽なんだね」
●「しかも、今回の問題では、各トッピングが対等なんですよ」
■「対等？ うん、確かに、トッピングごとの違いは全く無いね」
●「なので、”トッピング1がNG” と “トッピング2がNG” のパターン数は同じなんですよ！」
■「確かにそうだ。”1と2がNG” と “2と3がNG” も同じだね」
●「なので、” i 種類がNG” として、まとめて考えられるんですよ！」
■「えーっと、つまり、”とある i 種類の組み合わせがNG” のパターン数を ways(i) とすると、余事象はこうなるんだね」
$$\#(余事象)=\sum_{i=1}^N(-1)^{i-1}{}_NC_i\cdot ways(i)$$
●「そうですね。N_C_i は、”とある i 種類の組み合わせ” の選び方が N_C_i 通りあることを表すんですね。トッピングについて対称性があるとも言えますね」
■「解説pdfにもこんな感じの式があったけど、あれは余事象使ってなかったよね？」
●「いや、使ってますよ。今回の定義で、ways(0) が何を表すか、分かりますか？」
■「ways(0)？ うーん、”0種類がNG” で、それ以外のN種類はどうでもいいわけだから、”全種類どうでもいい” になって、実質、制限が無いのと同じ？ ってことは、全事象？」
●「そうです！ また、N_C_0=1 ですから、ways(0) – #(余事象) が答えになるんですよ」
■「そうか、だから、
$$答え=ways(0)-\sum_{i=1}^N(-1)^{i-1}{}_NC_i\cdot ways(i)$$
$$={}_NC_0\cdot ways(0)+\sum_{i=1}^N(-1)^i{}_NC_i\cdot ways(i)=\sum_{i=0}^N(-1)^i{}_NC_i\cdot ways(i)$$
になるんだね」
●「そうですね。ということは、今回は N ≦ 3000 なので、ways(i) が事前計算できていれば、ここに関しては O(N) で解けますね！」
■「なるほど、でも ways(i) の計算は難しそうだなあ」
●「ここまでも難しかったですけど、ここからが本番ですよ！」
■「ways(i) は、こんな感じだよね」
●「個々のマスはトッピングを、マス内の数字は、そのトッピングを食べる回数を表しているんですね」
■「うん。今は “とある i 種類の組み合わせについて、それらがNGである場合” を考えていて、選ぶ i 種類は何でも良いんだから、先頭の i 個にしても良いよね」
●「対称性のおかげですね！ 灰色になってる部分は、ways(i) だけを考える場合は、気にしなくても大丈夫ですよね」
■「そうだね。2回以上という条件を、達成していても、達成していなくても大丈夫だね」
●「でも、そう単純にもいかないんですよ」
■「え、どうして？」
●「ここからは先頭の i 種類にのみ注目したいんですけど、灰色部分の N-i 種類が ways(i) に与える影響を考慮しないといけないんです」
■「えっと、それは、N-i 種類は何でもいいんだから、2^(N-i) を掛けるとかで…… いや、そうか、何種類のラーメンを注文するかで影響が変わってくるのか！」
●「そうなんですよ。たとえば、N=8, i=5 で、ラーメンを 4 杯注文した場合を考えると、
oxxox|***
xoxxx|***
xxxxo|***
xxoxx|***
のようになって、どうでもいい部分（アスタリスクの部分）の選び方が、2^(3*4)=2^((N-i)*4) 通りあるんですよ！」
■「じゃあ、”ways(5) を 4 杯で達成する方法の数” には、2^((N-5)*4) を掛けないといけないけど、” 1 杯で達成する方法の数” には、2^(N-5) を掛けないといけないんだね」
●「つまり、 “ways(i) を j 杯で達成する方法の数” を考えないといけないんですね。これを ways2(i, j) と書くと、ways(i) はこうなりますね」
$$ways(i)=\sum_{j=?}^{?}2^{(N-i)j}ways2(i,j)$$
■「 j の値は、いくつからいくつまで考えればいいんだろう？」
●「それを考えるには、ways2(i, j) についてしっかり考えないといけないですね」
■「そもそも ways2(i, j) って何なんだろう？」
●「 i 種類のトッピングを、j 杯のラーメンに振り分ける方法、という感じでしょうか」
■「2つ以上のラーメンに振り分けちゃうと、前提に反するからダメだね。でも、どのラーメンにも振り分けられないトッピングはあっても良いんだよね？」
●「ですね。”1杯以下に乗っている” というのがNGの条件なので、”0杯のラーメンに乗っている” でも大丈夫ですね」
■「でもそれだと、” i 種類のトッピングが何も乗っていないラーメン” はいくらでも追加できるよね？」
●「でも N 種類のトッピング全体では、同じ組み合わせのラーメンがあるとダメなルールなので、2^(N-1) 通りのラーメンを任意に追加できるという感じですね」
■「うーん、ややこしいな……」
●「空ラーメンは厄介なので、とりあえず、ways2(i, j) を
i 種類のトッピングを j 杯のラーメンに振り分ける方法、ただし、どこにも属さないトッピングはあっても良い。ただし、j 杯の中にトッピングが無いラーメンがあってはいけない
としましょう。こうすると、j の最大値が i （もしくは N ）になります」
■「最後の “トッピングが無いラーメン” というのは、先頭 i 種類のトッピングが無いってことだよね。今は考慮していない N-i 種類のトッピングだけがあっても、それはダメってことだよね」
●「はい。N=8, i=5 のとき、
oxxox|oxx
は大丈夫ですが、
xxxxx|oxx
はダメです」
■「つまり、言い換えると、ways2(i, j) は “区別可能な i 個のモノを空でない j 組のグループに分ける方法の数、ただし、どこにも属さないモノがあってもいい” ということだね」
●「これが、第2種スターリング数に似ているらしいんですよ」
■「第2種スターリング数？」
■「スターリングって、階乗の近似の人？」
●「スターリングの近似と同じ人っぽいですね」
■「で、スターリング数って何なの？」
●「ここにWikipediaの記事があります」
第2種スターリング数 (Stirling number of the second kind) は、 を下降階乗冪 の級数:
で展開したときの展開係数として定義される。
■「うーん、よく分からないな……」
●「そこじゃなくて、その下の『組み合わせ数学における意味』の部分を見てみましょう」
第2種スターリング数 は、組合せ数学において、番号づけされた 個の要素をグループ 個に分割する組み合わせの数を与える。 分割する要素は番号付けされているので個別に区別できるが、グループは順序を特に区別しないものとする。
（中略）
要素 0, 1, 2, 3 をグループ2個に分割する組み合わせは、全部で以下の7通りがある。
![{\begin{array}{llll}{}[(0),(1,2,3)],&[(1),(0,2,3)],&[(2),(0,1,3)],&[(3),(0,1,2)],\\{}[(0,1),(2,3)],&[(0,2),(1,3)],&[(0,3),(1,2)]\end{array}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6177233a5fdc5066b8304ae6ce8f10a1618656d)
■「なるほど、確かに似てるね」
●「ways2(i, j) との違いは、どこにも属さない要素があってはいけないというところですね」
■「第2種スターリング数には漸化式があるみたいだね。ということは、ways2(i, j) にも漸化式は作れるのかな」
●「できそうですね。要素 i 個を j グループに分割する方法は、
① i 番目の要素が、要素数1のグループを作る
② i 番目の要素が、要素数2以上のグループに属する
③ i 番目の要素が、どのグループにも属さない
の背反な3通りに分けられますよね」
■「そうだね。どれも被りが無いし、たぶん漏れも無いね」
●「①の場合は、i 番目の要素を抜いて考えると、i-1 個の要素が j-1 個のグループに分割されていますね」
■「 i 番目を追加することで j グループになるんだね」
●「②の場合は、i 番目の用をを抜いても、i-1 個の要素が j 個のグループに分割されていますね」
■「 i 番目の要素は、グループ数を増やすことに貢献しないんだね」
●「③の場合も同じですね。ただし、②の場合は、i-1 個の要素が振り分けられている j 個のグループのどれに i 番目の要素が入るか、によって分け方が変わりますよね」
■「そうだね。でも③の場合は “どこにも属さない” の一択だから関係ないね。じゃあ、漸化式はこんな感じか」
$$ways2(i,j)=ways2(i-1,j-1)+(j+1)\cdot ways2(i-1,j)$$
●「そうですね！ 端の値はどうなるでしょう。ways2(0, 0), ways2(i, 0), ways(i, i) あたりが問題ですか」
■「ways(0, 0) は、0種類を0グループに分割か。”グループが何もない” の 1 通りってことになるのかな？」
●「そんな気がしますね。後で確認しましょう」
■「 i ≠ 0 のときの ways(i, 0) は、要素 i 個を 0 グループに分割するんだけど、今回は “どこにも属さない要素があってもOK” だから、同じく “グループが何もない” の 1 通りかな」
●「ways(i, i) は、全要素が単独でグループになる場合しか無いので、1通りですね。ちなみに、i < j のときは、ways(i, j) は 0 ですね。空のグループがあるといけないので」
■「そうだね。これで、ways2(i, j) が、漸化式で全部計算できることになるんだね」
●「 i も j も 0 から N まで考えればいいので、O(N^2) ですね。間に合います！」
■「それで、空のラーメンの件はどうなったんだっけ」
●「あ、そうでしたね。ways(i) を構成する選び方として、今は i 種類のトッピングが1つ以上含まれるラーメンを j 杯使う場合を考えていました。そこに、i 種類のトッピングを使わない（残りの N-i 種類のトッピングのみで構成される）ラーメンを好きなだけ追加しても問題ないんですよね」
■「そうだね。それで、追加できるラーメンは 2^(N-i) 種類あるんだよね」
●「はい。N-i 通りのトッピングから好きに選んだラーメンですからね」
■「じゃあ、2^(N-i) 通りの中から追加するかしないかを選ぶことになって、ways(i) が 2^(2^(N-i)) 倍になるのか」
●「そうですね。これが正確ですね」
$$ways(i)=2^{2^{N-i}}\sum_{j=0}^{N}2^{(N-i)j}ways2(i,j)$$
■「 j の最大値は i でも大丈夫だよね」
●「ですね。ways2(i, j) は j > i の範囲で 0 ですからね」
■「ways2(i, j) の漸化式と、この ways(i) の式と、包除原理の式でこの問題は解けるんだね」
●「はい。ただ、剰余については少し注意しないといけませんね」
■「ああ、二項係数（コンビネーション）の剰余と、2^(2^(N-i)) の剰余が出てくるね」
●「二項係数の剰余は、階乗の逆元で求められますね。こちらのpdfにも詳しく記載されています。n! の剰余とmod逆元を、あらかじめ計算しておけば大丈夫ですね」
$$n!\equiv (n-1)!\cdot n$$
$$(n!)^{-1}\equiv ((n-1)!)^{-1}\cdot n^{-1}$$
■「なるほど、
$${}_nC_r=\frac{n!}{r!(n-r)!}\equiv n!\cdot (r!)^{-1}\cdot (n-r)!^{-1}$$
で計算できるんだね」
●「2^(2^(N-i)) ですけど、これはフェルマーの小定理が使えますね」
■「逆元ってこと？」
●「そうじゃなくて、単純に、mod M で
$$2^{M-1}\equiv 1$$
が成立するので」
■「ああ、じゃあ
$$2^{2^{N-i}}=2^{M-1}\cdot 2^{M-1}\cdot\cdots\cdot 2^{\left (2^{N-i}\%(M-1)\right )}\equiv 2^{\left (2^{N-i}\%(M-1)\right )}$$
が成立するんだね」
●「さあ、コーディングしますよ！」
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include <iostream> #include <vector> using namespace std; #define repr(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) for(int i=0;i<n;i++) using ll = long long; using vll = vector<long long>; using vvll = vector<vector<long long>>; // 1～nのmod逆元を計算する(modは素数), O(n) void ModInv(int n, vector<ll> &inv, int mod) { inv[0] = 0; inv[1] = 1; for (int i = 2; i <= n; i++) { inv[i] = mod - ((mod / i) * inv[mod % i] % mod); } } // 0!～n!のmod逆元を計算する(modは素数), O(n) void FacInv(int n, vector<ll> inv, vector<ll> &fac, vector<ll> &facInv, int mod) { fac[0] = facInv[0] = 1; for (int i = 1; i <= n; i++) { fac[i] = (fac[i - 1] * i) % mod; facInv[i] = (facInv[i - 1] * inv[i]) % mod; } } // nCkをmodで割った余りを求める。mod素数限定 // ModInv()とFacInv()が必要 ll CombiMod(int n, int k, int mod, const vll &inv, const vll &fac, const vll &facInv) { if (n == 0 && k == 0) return 1; if (n <= 0 || k < 0 || k > n) return 0; if (k == 0) return 1; return (((fac[n] * facInv[k]) % mod) * facInv[n - k]) % mod; } // 繰り返し二乗法で (x^n)%mod を計算する O(log n) ll powMod(ll x, ll n, ll mod) { ll res = 1; while (n > 0) { if (n & 1) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } int main() { int N, M; cin >> N >> M; // 階乗逆元の事前計算 vector<ll> inv(N + 1); vector<ll> fac(N + 1); vector<ll> facInv(N + 1); ModInv(N, inv, M); FacInv(N, inv, fac, facInv, M); vll ways(N + 1, 0); vvll ways2(N + 1, vll(N + 1, 0)); // ways2 の事前計算 ways2[0][0] = 1; repr(i, 1, N + 1) { rep(j, N + 1) { if (j > i) { ways2[i][j] = 0; } else if (j == 0 || j == i) { ways2[i][j] = 1; } else { ways2[i][j] = (((j + 1) * ways2[i - 1][j]) % M + ways2[i - 1][j - 1]) % M; } } } /* // ways2 のデバッグ用出力 rep(i, N + 1) { rep(j, N + 1) { cerr << ways2[i][j] << " "; } cerr << endl; } */ // ways の事前計算 rep(i, N + 1) { rep(j, i + 1) { // ways2(i,j)*2^((N-i)j) を足す ways[i] += ways2[i][j] * powMod(2, (ll)(N - i) * j, M); ways[i] %= M; } // 2^(2^(N-i)) を掛ける ways[i] *= powMod(2, powMod(2, N - i, M - 1), M); ways[i] %= M; } // 余事象と包除原理に基づいて答えを計算 ll ans = 0; rep(i, N + 1) { // 今回足し引きする値（Σの中身） ll val = (CombiMod(N, i, M, inv, fac, facInv) * ways[i]) % M; // i の偶奇で足し引きを切り替える if (i % 2 == 0) { ans = (ans + val) % M; } else { ans = (ans - val + M) % M; } } cout << ans << endl; return 0; } |
●「ACです！ やりました！」
■「おおー 途中の ways2 を出力する部分も、ちゃんと正しい値を返していたね」
●「いやー、疲れました。難しかったですねー」
■「そうだね。ヒント無しで自力で解くのは厳しかったな」
●「でも分かってしまえば解けそうな気もしてくるなー 悔しー！」
■「次に包除原理の問題に当たったときは、解けるようになっておきたいね」
●「AGCで包除原理来い！」