目次
estie プログラミングコンテスト2024 （AtCoder Regular Contest 188）A,B,C,D問題メモ
estie プログラミングコンテスト2024 （AtCoder Regular Contest 188）
ちゃんとした証明ができてないまま解いてるんだよな。
A - ABC Symmetry
問題文
- A, B, C からなる空でない文字列 $T$ に対して、以下の $2$ 種類の操作を好きな順で好きな回数だけ行い、空文字列とすることができる時、これを「よい文字列」と呼びます。
- 操作 $1$ ：文字列に存在する同一の文字を $2$ つ選び、削除する（同一の文字が $2$ つ以上ない場合は行えない）
- 操作 $2$ ：文字列に存在する A, B, C を $1$ つずつ選び、削除する（A, B, C がそれぞれ $1$ つ以上ない場合は行えない）
- 例えば、ABACA は、次のように操作を行うことで空文字列にできるため、よい文字列です。
- $2,4,5$ 文字目を選んで削除する（操作 $2$）。文字列は AA になる。
- $1,2$ 文字目を選んで削除する（操作 $1$）。文字列は空文字列になる。
- A, B, C, ? からなる長さ $N$ の文字列 $S$ が与えられます。
- ? をそれぞれ A, B, C のいずれかに置き換えてできる文字列であって、よい文字列を連続する部分文字列として $K$ 個以上含むものはいくつあるでしょうか。答えを $998244353$ で割った余りを求めてください。
- ただし、同じ文字列であるような部分文字列であっても、元の文字列内での位置が異なる場合は別々に数えます。
制約
- $1 \leq N \leq 50$
- $0 \leq K \leq N(N+1)/2$
- $N,K$ は整数である
- $|S|=N$
- $S$ は A, B, C, ? からなる文字列である
解法
「全ての置き換えに対する良い部分文字列の総和」とかだと主客転倒が使えそうだけど、 今回は「1つ1つの置き換え方に $K$ 個以上含むかどうか」なので筋が悪い。
まずは単純に、文字列が ? を含まず「ABCからなる文字列に、良い部分文字列が何個含まれるか」を求める方法を考える。
$N$ が小さいので $O(N^3)$ かければそりゃいけるんだけど、
DPっぽく解く方法を探るため、先頭から1文字ずつ見ていくような方法でなるべく考える。
良い文字列は、言い換えると「含まれる A,B,C の個数の偶奇が一致する」である。
このため、途中で良い文字列が出現したら、貪欲に確定して問題ない。
A B C A A B ... という文字列は、先頭から見ると ~~~~~~~ ~~~~ ABC, 続く AA の時点で良い文字列が現れる。
この時、「ABCAAB」までの状態を「(いくつかの良い文字列の連続) + 余り B」とまとめてしまって問題ない。
この後に「ABCAABABA…」など続くとして、「ABC,AA を先に消したら残りの文字列を全て消せなくて、消す文字の組や順番を変えたら全て消せる」ということは発生しない。
なので、「いい文字列にならずに余っている文字片の中で奇数個使われているもの」で場合分けでき、 その候補は (なし),A,B,C,AB,AC,BC の7通りしかない。
以下の2つ（8つ?）を状態に持てばよい。
- 右端を $r$、左端を $1 \le l \lt r$ とした文字列それぞれの内、余っている文字片で奇数個使われている文字の組が（上記の7通り）であるものがそれぞれ何個あるか
- ここまでで確定した良い文字列の個数
A B C A B 余り文字片 状態
~ B
~~~~ AB
~~~~~~~ なし → {なし:1, B:2, AB:2} 確定:3
~~~~~~~~~~ B
~~~~~~~~~~~~~ AB
※確定した個数は、ここまでの過程で、
ABCまで進めたときに1個、ABCAの時にBCAで1個、ABCABの時にCABで1個、
計上されている
■次の文字がBのとき、このように更新できる
旧状態 新状態
なし:1 → B:1
B:2 → なし:2, 2個追加で確定 → {なし:2, A:2, B:2} 確定:5
AB:2 → A:2
その文字(B)から始まるのを1つ追加
この「7通りの文字片の個数 + 確定文字列数」を1つの状態とすると、先頭から順に更新しながら良い部分文字列を数えられる。
この方法なら、? が入った時を考えてもDPしやすい。
- $\mathrm{DP}[i,X]:=S_i$ まで見て、状態が $X$ であるものの個数
$S_i=$ ? である箇所は、? を A,B,C と仮定した3通りそれぞれに遷移すればよい。
最終的に、確定文字列数が $K$ 以上になるものを合計すれば答えとなる。
懸念点は状態数が多くなりすぎてTLEにならないか？ ということ。
この正確な見積もりが難しくて二の足を踏んでいたが、結局、実装したら通った。
$S$ が50個の ? からなる場合が最も状態数が多くなる。
その場合の $(i,X)$ の組は実験すると約 $10^6$ 通り程度となった。
更新に「? の置き換え方3通り × 各文字片の遷移 7」程度の定数倍をかけても間に合うことがわかる。
「7通りの文字片の状態」は、雑に見積もれば ${}_7\mathrm{H}_N$ くらいあるはずだが、 実際は極端に偏ることは起こりにくいこと、 また「確定文字列数」も、$i$ が進むと全く確定しないことはあり得ないため、$i$ ごとにおよそ範囲は絞られてくることが、 状態数が抑えられた理由かもしれない。
状態数を節約した解法
余っている文字片のうち、反転させた組（A と BC、B と AC、C と AB）は、「次に何が来たら良い文字列になるか」という点でそれぞれ同一視できる。
これにより、文字片のパターンは 7通りでなく4通りの状態で管理できる。
さらに、良い文字列の確定は1文字毎におこなう必要は無い。
先頭からの累積和の差分で区間和が計算できるように、先頭から見て同じ文字片が余った同士の組が、良い文字列と考えることができる。
（$S[1:l]$ ではAが余った状態、$S[1:r]$ でもAが余った状態だった場合、$S[l+1:r]$ は良い文字列）
S A B C A B B
余り - A C - A C A
(--------] →ABC
(--------] →BCA
(-----] →BB
よって、「文字片が (-,A,B,C) であったそれぞれの回数」を記録しておけば、最終結果から良い文字列の個数は計算できる。
この方法なら、状態数が $O(N^4)$ であると明確に見積もれる。
B - Symmetric Painting
問題文
- 円周上を $N$ 等分する位置に、点 $0,1, \ldots , N-1$ がこの順に並んでおり、Alice が点 $0$ に、Bob が点 $K$ にいます。
- 初め全ての点は白色に塗られています。
- 両者は、Alice から始めて交互に次のような操作を行います。
- その時点で白色である点を $1$ つ選び、黒色に塗る。ただし、操作後に、操作者と円の中心を結ぶ直線に対して、各点の色が線対称でなければいけない。
- 操作者が上記の条件を満たす操作ができなければ、そこで一連の操作を打ち切ります。
- 両者とも、最終的に最も多くの点を黒く塗ることができるように協力して最善の選択をします。一連の操作が全て終了したときに全ての点を黒く塗ることができているかどうかを求めてください。
- $T$ 個のテストケースが与えられるので、それぞれについて答えてください。
制約
- $1\leq T\leq 10^5$
- $2\leq N\leq 2\times 10^5$
- $1\leq K\leq N-1$
- 入力される値はすべて整数である
解法
- シミュレーションを実装します。
- 結果を観察します。
- $N$ が4の倍数の時、NG
- $N$ が2x奇数の時、$\mathrm{GCD}(N/2,K)=1$ ならOK、それ以外はNG
- $N$ が奇数の時、$\mathrm{GCD}(N,K)=1$ ならOK、それ以外はNG
- 投げると通ります。
AC数もA問題より多いため、「証明は難しいけど、実験からそれらしき法則性を見つけるのは簡単」タイプの問題のように思う。
略証
Aliceは、初手で $0$ か、$N$ 偶数の場合に $N/2$ を塗るしか方法がない。
対象なので、$0$ を塗るとする。
すると、Bobが塗れるのは一意に決まり、$2K$ となる。しばらくは両者選択肢がなく、
- $0,2K,-2K,4K,-4K,...$（mod N）
と塗られていく。
この流れは $\mathrm{GCD}(N,2K)$ おきに点が塗られた状態で、
次に塗られようとする頂点が既に塗られたものとなり、いったん終了する。
ここまでを「1ループ」とする。
$\mathrm{GCD}(N,2K)=1$ なら全てが塗られているためOK。
それ以外の時は、まだ白い点が残っている。
- $N$ が奇数の時
- $K$ は $\mathrm{GCD}(N,2K)$ の倍数なので、既に塗られている。
- 奇数個の点が塗られるので、次はBobの番だが、操作できない。
- →NG
- $N$ 偶数で、塗られた個数 $\dfrac{N}{\mathrm{GCD}(N,2K)}$ が偶数の時
- 次にAliceの手番だが、対称的に塗られているため、$0,N/2$ の両方が既に塗られている。
- →NG
- $N$ 偶数で、塗られた個数 $\dfrac{N}{\mathrm{GCD}(N,2K)}$ が奇数の時
- 次Bobの手番
- 奇数個の点を配置するので、
- $\mathrm{GCD}(N,2K)$ の倍数の点が塗られていて、その対象位置の点は塗られていない。
- 特に $K$ とその対象位置の点は、一方が塗られてもう一方が塗られていない。
- Bobからもう1ループできる。
- このループでは、1回目のループの対象位置の頂点が全て塗られる。
- 次Aliceの手番ではもう操作できない。
- →2ループで全てが塗られた状態になっていないといけない
- →$\mathrm{GCD}(N,2K)=2$ ならOK
C - Honest or Liar or Confused
問題文
- $1$ から $N$ までの番号がついた $N$ 人の村人が住む村があります。
- 各村人は、正直者であるか嘘つきであるかのどちらかです。また、村人のうち何人かは混乱しています。
- あなたは、村人による証言を $M$ 個手に入れました。証言は $A_i, B_i, C_i$ で与えられ、以下を表します。
- $C_i=0$ であれば、村人 $A_i$ が村人 $B_i$ を正直者であると証言した
- $C_i=1$ であれば、村人 $A_i$ が村人 $B_i$ を嘘つきであると証言した
- 村人は、次のような規則で証言を行います。
- 混乱していない正直者は必ず正しい証言をする。
- 混乱していない嘘つきは必ず嘘の証言をする。
- 混乱している正直者は必ず嘘の証言をする。
- 混乱している嘘つきは必ず正しい証言をする。
- 証言に矛盾しない「混乱している村人の組」を1つ、求めてください。
- 矛盾しないとは、「混乱している村人の組」を決めたとき、「正直者である村人の組」を上手く決めれば、全ての証言が上記の規則にしたがうようにできる事を指します。
- ただし、どのような村人の組が混乱しているとしても与えられた証言の組が矛盾する場合は、そのことを指摘してください。
制約
- $2 \leq N \leq 2 \times 10^5$
- $0 \leq M \leq \mathrm{min} \lbrace 2 \times 10^5,N(N-1) \rbrace $
- $1 \leq A_i, B_i \leq N, A_i \neq B_i$
- $i\neq j$ のとき $A_i\neq A_j$ または $B_i\neq B_j$
- $C_i=0$ または $C_i=1$
- 入力される値はすべて整数である
解法
混乱というステータスがない問題は、2-SATで解ける。
- 各人が「正直者である」ことを表す $N$ 個の真偽値変数 $x_1,...,x_N$ を用意する。
- 証言に1つごとに、2つの変数が等しいかどうかの制約がかかる。
- $i$ が $j$ を正直者といった場合、$x_i=x_j$ である（$i$ 正直なら $j$ も正直、嘘つきなら嘘つき）
- $i$ が $j$ を嘘つきといった場合、$x_i \neq x_j$ である（$i$ 正直なら $j$ は嘘つき、嘘つきなら正直）
- $i→j$ の方向の制約であるとともに、$j→i$ の方向の制約でもある。
- 全ての制約を満たす真偽値の割り当てが可能なら、割り当て例を1つ答える。
混乱を考慮する場合、1人にもう1変数、「混乱していない」という状態を表す変数 $y_i$ を追加したくなるが、 これだと2-SATで解けるような単純な形式で辺が張れなくなる。
- $i$ が $j$ を正直者といった場合
- $i$ が正直で、混乱していなければ、$j$ は正直者 $(x_i \& y_i) \Rightarrow x_j$
- $i$ が正直で、混乱していれば、$j$ は嘘つき $(x_i \& \neg y_i) \Rightarrow \neg x_j$
- $i$ が嘘つきで、混乱していなければ、$j$ は嘘つき $(\neg x_i \& y_i) \Rightarrow \neg x_j$
- $i$ が嘘つきで、混乱していれば、$j$ は正直者 $(\neg x_i \& \neg y_i) \Rightarrow x_j$
前提の項が2つの & 条件になってしまう。
また、$x_j$ が True となりうるパターンが2つ存在するため、$j→i$ の制約も張れなくなる。
代わりに「$i$ は真実を証言する人である」を表す変数を $z_i$ とし、$\{x,z\}$ の $2N$ 個の変数を用いると、上手くいく。
- $i$ が $j$ を正直者といった場合、$z_i = x_j$ である
- $i$ が $j$ を嘘つきといった場合、$z_i \neq x_j$ である
これなら、混乱がない状態のような制約で証言を処理できる。
この 2-SAT を解いて、矛盾すれば解無し。
解があれば、その割り当ての1つを取り出して、$x_i \ \mathrm{xor} \ z_i$ が、その人が混乱していたことを表すことになる。
解法2
2-SAT でも解けるが、2部グラフ判定問題と考えても解ける。
- $i$ が $j$ を正直者といった場合、$z_i$ と $x_j$ は同じグループに属する
- $i$ が $j$ を嘘つきといった場合、$z_i$ と $x_j$ は違うグループに属する
ポテンシャル付きUnion-Findなどで、
証言に従って同じグループに属する間に“0”の辺、
異なるグループに属する間に“1”の辺を張っていく。
$d(u,v)$ を「2点間を結ぶパス上の辺の値の総XOR」としたとき、
「$d(u,v)=0$ である2点間に“1”の辺を張ろうとする」
「$d(u,v)=1$ である2点間に“0”の辺を張ろうとする」ことが発生すれば矛盾。
そうで無い場合、$i=1,2,...,N$ の順に
- $x_i,z_i$ が連結なら、$d(x_i,z_i)$ が混乱の有無
- $x_i,z_i$ が非連結なら、適当に $0,1$ のどちらかに決め、$x_i,z_i$ をその値で結ぶ
としていけばよい。
D - Mirror and Order
問題文
- 長さ $3$ の $N$ 個の数列の列 $X$ が以下の条件を満たすとき、$X$ は「よい数列の列」であるといいます。
- 条件: $i$ 個目の数列の第 $j$ 項を $X_{i,j}$ としたとき、
- $(X_{1,1},X_{2,1},...,X_{N,1})$ に $1$ から $N$ までの整数がちょうど $1$ 回ずつ現れる
- $(X_{1,2},X_{2,2},...,X_{N,2})$ に $1$ から $N$ までの整数がちょうど $1$ 回ずつ現れる
- $(X_{1,3},X_{2,3},...,X_{N,3})$ に $1$ から $N$ までの整数がちょうど $1$ 回ずつ現れる
- よい $X$ から、以下のように数列 $a=(a_1,a_2, \ldots ,a_N), b=(b_1,b_2,\ldots ,b_N)$ を定義します。
- $N$ 個中 $i$ 番目の数列を $s_i$ 、$i$ 番目の数列を逆順にしたものを $t_i$ とする。
- これらを全て辞書順に並べた時、$s_i$ が $a_i$ 番目、$t_i$ が $b_i$ 番目である。
- ただし、$2N$ 個の数列の中に同一の数列が $2$ 個以上存在する場合には、$a, b$ は定義されない。
- したがって、$a, b$ が定義される場合には、$a$ と $b$ を合わせた数列には $1$ から $2N$ までの整数がちょうど $1$ 回ずつ現れます。
- 長さ $N$ の数列 $A,B$ が与えられます。
- ただし、$A$ の各項は $1$ 以上 $2N$ 以下の整数であり、$B$ の各項は $1$ 以上 $2N$ 以下の整数または $-1$ です。
- また、$A$ と $B$ を合わせた数列には $-1$ 以外の整数は $1$ 回以下しか現れません。
- $i=1～N$ に対して次の条件を満たすような $a,b$ を考えます。
- $a_i = A_i$
- $B_i \neq -1$ ならば $b_i = B_i$
- このうち、「よい数列の列」から定義された結果としてありえるような $(a,b)$ の個数を求めてください。
- 答えを $998244353$ で割った余りを求めてください。
制約
- $2\leq N\leq 3000$
- $1\leq A_i\leq 2N$
- $1\leq B_i\leq 2N$ または $B_i=-1$
- $A$ と $B$ を合わせた数列には $-1$ 以外の整数は $1$ 回以下しか現れない。
- 入力される値はすべて整数である
解法
ちょっと問題文が複雑。
よい $X$ の個数ではなく、そこから定義されうるような $(a,b)$ の個数の方を求める。
判定問題
まず、ある $(a,b)$ に対し、それが「よい $X$ から定義された数列」として適切かどうかを判定する問題を考える。
$s_i$ の先頭には $1～N$ が1つずつ、$t_i$ の先頭にも $1～N$ が1つずつ出現する。
これを辞書順に並べると、
- $1,2$ 番目は先頭が“1”であり、どちらかが $s$ 由来でどちらからが $t$ 由来
- $3,4$ 番目は先頭が“2”であり、どちらかが $s$ 由来でどちらからが $t$ 由来
- …
- $2N-1,2N$ 番目は先頭が“N”であり、どちらかが $s$ 由来でどちらからが $t$ 由来
となる。したがって、以下の制約が生じる。
- 制約: $a$ は $(1,2),(3,4),...,(2N-1,2N)$ の各組から1つずつ選ばれていないといけない。
また、$a_i=3,b_i=4$ など、先頭要素が同じになる2つの順位が、ともに $a_i,b_i$ に割り当てられていてもいけない。
この場合、$s_i=t_i$ となり、同じ数列が含まれることで $a,b$ が定義されなくなる。
- 制約: $\frac{a_i+1}{2}$ と $\frac{b_i+1}{2}$（それぞれ切り捨て）は異なっていないといけない。
ここまでの制約を満たすような $(a,b)$ からは、元の $X$ の真ん中の要素 $X_{i,2}$ の大小関係が部分的にわかる。
$1～N$ を頂点として小→大の有向辺で大小関係を表すことを考える。
i 1 2 3 4
a 1 3 6 7 ,------1-----v
先頭 1 2 3 4 → ① <--2-- ② ③ <--3-- ④
^-----4-----'
b 4 8 2 5
先頭 2 4 1 3 辺上の数字は、どの先頭要素が同じ組によって張られた辺か
たとえば、$s_1$ の先頭要素と $t_3$ の先頭要素は 1 で共通し、$s_1$ の方が辞書順で先なので、 真ん中の要素は $X_{1,2} \lt X_{3,2}$ とならないといけない。よって①→③に辺が張られる。
このようにしてできるグラフは、置換グラフの各辺に向きを付けたものとなる。
要は、いくつかの無向サイクルからなる。
（※ここでは「無向サイクル」を、「有向グラフから辺の向きを無視したときに閉路となっているもの」として使っている）
この無向サイクルが、向きを戻したときに（有向）サイクルとなっている場合、
つまり全て同じ向きの有向辺からなる場合、大小関係がループするので矛盾する。
逆に、向きが異なる辺が混在するときは、大小関係を割り当てられる。
複数の大小関係のマージはいかようにもできるので、1つ1つの無向サイクルを独立に調べてよい。
矛盾 OK ①→②→③ ①→②←③ ↑ ↓ ↑ ↑ ⑥←⑤←④ ⑥→⑤←④
また、自己辺がある場合というのは $s_i=t_i$ により $(a,b)$ が定義されない場合に該当するので、 （長さ1であっても）「サイクルができてはいけない」という条件にまとめられる。
結局、$(a,b)$ に、元となるよい数列の列が存在する条件は、
- $(1,2),(3,4),...,(2N-1,2N)$ の各組が、それぞれ $a,b$ に分散していること
- 真ん中の要素の大小関係を表した有向グラフで、サイクルができないこと
を満たせばよいことがわかる。
問題の言い換え
その上で、次は元の問題に戻って、一部が“-1”で隠された $A,B$ で適切な $(a,b)$ となるものの個数を考える。
$A$ は全て分かっているので、1つめの条件は簡単にチェックできる。
2番目の条件が難しい。
$A_i$ により、各 $i$ からは、自身と、（未確定かもしれないが、いずれかの）対応する $j$ を結ぶ辺が、どちら向きに張られるかが分かる。
$(2x-1,2x)$ の組の内、$A_i$ が $2x-1$ 側なら流出辺、$2x$ 側なら流入辺が張られることになる。
i 1 2 3 4
A 1 3 6 7 v-----4-----,
先頭 1 2 3 4 → ① ② ③ ④
出入 出 出 入 出 ↓ ↓ ↑
B -1 8 -1 -1
先頭 4
この時、以下のように色で分けて考えることにする。
- $A_i$ が $2x-1$ 側だったことによる流出辺を「白い辺」
- $A_i$ が $2x$ 側だったことによる流入辺を「黒い辺」
各頂点からは、$A_i$ の値に従って1本の白または黒い辺が出て、
またそれ以外に、他の頂点からの1本の白または黒い辺を受け入れる。
したがって、$A,B$ の情報からつなげる辺はつないだ後の各連結成分は、以下のいずれかの状態である。
- 全ての流入・流出辺は確定済みで1つのサイクルが完成している
- 白い辺または黒い辺が1本出ていて、また1本の受け入れ余地を残す
未確定の辺も確定した結果、白い辺だけ、または黒い辺だけでできたサイクルができてしまうと、不適切な $(a,b)$ となる。
逆に、全てのサイクルが白黒辺が混在した状態であれば良い。
よって、もし既に「白い辺だけ、または黒い辺だけの完成したサイクル」ができてしまっている場合は0通り。
それ以外の場合、未完成の部分的な連結成分を、以下のように分類してカウントする。
- （相手先が決まっていない辺を含め）白い辺のみからなる連結成分 $N_0$
- （相手先が決まっていない辺を含め）黒い辺のみからなる連結成分 $N_1$
- 白と黒が混在する連結成分 $N_2$
各連結成分をどこにつなぎに行くかは $(N_0+N_1+N_2)!$ 通りあり、$B$ に含まれる“-1”の決め方に対応する。
このうち、白い連結成分同士、黒い連結成分同士でサイクルが完結してしまうようなつなぎ方がアウト。
サイクルができないつなぎ方の個数が、答えとなる。
求解
「サイクルができない」は数えにくいので、「少なくとも $k$ 個、サイクルができるようなつなぎ方の数」を $k$ 毎に求められれば、包除原理が使える。
白い連結成分から $n_0$ 個取り出し、$k_0$ 個のサイクルを作るような場合の数は、第1種スターリング数と一致する。
これを $S[n_0,k_0]$ と表すとして、黒からも $n_1$ 個で $k_1$ 個のサイクルを作る場合を考えると、答えは以下になる。
- $\displaystyle \sum_{n_0=0}^{N_0}\sum_{k_0=0}^{n_0}\sum_{n_1=0}^{N_1}\sum_{k_1=0}^{n_1} (-1)^{k_0+k_1} {}_{N_0}\mathrm{C}_{n_0} S[n_0,k_0] {}_{N_1}\mathrm{C}_{n_1} S[n_1,k_1] (N_0+N_1+N_2-n_0-n_1)$
$n_0,k_0,n_1,k_1$ の4つの変数が動くので、そのままだと $O(N^4)$ となりとても間に合わない。
2次元FFTを使って、${}_{N_0}\mathrm{C}_{n_0} S[n_0,k_0]$ と ${}_{N_1}\mathrm{C}_{n_1} S[n_1,k_1]$ を畳み込んで、 「白黒どっちでもいいので、$n$ 頂点使って $k$ 個ループができる場合の数」という情報に集約すれば、$O(N^2)$ で求められる。
ただ、Pythonでは重めの $O(N^2 \log{N})$ はTLEで通らなかった。3～4秒あれば、、、といったところ。
実はこの式は、スターリング数の性質を使って、劇的に計算量を減らせる形となっている。
$n_0,n_1,k_1$ が固定され、$k_0$ だけが動くと考えたとき、次のような式となる。
- $\displaystyle \sum_{k_0=0}^{n_0} (-1)^{k_0} S[n_0,k_0] \times ((-1)^{k_1} {}_{N_0}\mathrm{C}_{n_0} {}_{N_1}\mathrm{C}_{n_1} S[n_1,k_1] (N_0+N_1+N_2-n_0-n_1))$
そして、スターリング数の性質から、以下が成り立つ。
- $n \ge 2$ のとき、$\displaystyle \sum_{k=0}^{n} (-1)^{k} S[n,k]=0$
よって、Σを展開したほとんどの項が消える。
これは $k_1$ に対しても成り立つので、結局、$n_0,n_1 \in \{0,1\}$ 場合のみ考慮すればよいということになる。
