D - AND OR Equation Editorial
by 
maspy
[1] 集合による言い換え
\(0\) 以上 \(2^N-1\) 以下の非負整数を，ビット列によって \(S = \{0, 1, \ldots, N - 1\}\) の部分集合に対応させます．\(S\) の部分集合全体を \(2^S\) と書くことにすると，本問題は次のように言い換えることができます：
\(f\colon 2^S\longrightarrow \{0,1,\ldots,K\}\) であって以下の条件を満たすものを数え上げよ．
- 任意の \(A, B\in 2^S\) に対して \(f(A)+f(B)=f(A\cap B)+f(A\cup B)\).
[2] 解の特徴付け
次を証明することができます．
\(f\colon 2^S\longrightarrow \mathbb{Z}\) が任意の \(A, B\in 2^S\) に対して \(f(A)+f(B)=f(A\cap B)+f(A\cup B)\) を満たすとする．\(c = f(\emptyset)\), \(x_i = f\bigl(\{i\}\bigr) - c\) (\(0\leq i<N\)) とすれば，任意の \(A \in 2^S\) に対して \(f(A) = c + \sum_{i\in A}x_i\) が成り立つ．
このことを証明しましょう． \(g(A) = f(A) - c\) として \(g\colon 2^S\longrightarrow \mathbb{Z}\) を定めると，次が成り立ちます．
- \(g(\emptyset) = 0\).
- 任意の \(A,B\in 2^S\) に対して \(g(A)+g(B)=g(A\cap B) + g(A\cup B)\).
- \(g\bigl(\{i\}\bigr) = x_i\).
さらに 1. と 2. より，次が分かります：\(A\cap B = \emptyset\) ならば \(g(A)+g(B) = g(A\cup B)\). この性質から
\[g(A) = g\biggl(\bigcup_{i\in A}\{i\}\biggr) = \sum_{i\in A}g\bigl(\{i\}\bigr) = \sum_{i\in A} x_i\]
が分かるので，\(f(A) = c + \sum_{i\in A}x_i\) が示されました．
逆に，次も成り立ちます：
\(c, x_0,\ldots, x_{N-1}\in \mathbb{Z}\) に対して \(f(A) = c + \sum_{i\in A}x_i\) として \(f\colon 2^S\longrightarrow \mathbb{Z}\) を定めると，任意の \(A, B\in 2^S\) に対して \(f(A)+f(B)=f(A\cap B)+f(A\cup B)\) が成り立つ．
実際，\(c\) および各 \(x_i\) の両辺への寄与を個別に考えることで容易に証明できます．
[3] 問題の言い換え
[2] により，問題の数え上げは次のように言い換えられます．
整数の組 \((c, x_0, x_1, \ldots, x_{N-1})\) で次を満たすものを数えよ： 任意の \(A\in 2^S\) に対して \(0\leq c + \sum_{i\in A}x_i\leq K\).
\(x_i < 0\) であるような \(i\) に対する \(x_i\) の総和を \(s^{-}\), \(x_i > 0\) であるような \(i\) に対する \(x_i\) の総和を \(s^{+}\) とすれば，この不等式は \(0\leq c + s^{-}\) かつ \(c + s^{+}\leq K\) つまり \(-s^{-}\leq c\leq K - s^+\) と変形できます．そのような \(c\) の個数は \(\max\{0, K + 1 - s^+ + s^-\}\) です．
\(s^+ - s^- = \sum_{i} \lvert x_i\rvert\) なので，本問題は次のように言い換えることができます．
\(\sum_i\lvert x_i\rvert \leq K\) であるような整数の組 \((x_0, \ldots, x_{N-1})\) すべてに対する，\((1+K-\sum_{i}\lvert x_i\rvert)\) の総和を求めよ．
[4] 答の計算
\(2\) つの方法を紹介します．
方法 1
\(x_i \neq 0\) となる \(i\) の個数 \(n\) を定めた上で数え上げます． \(i\) の選び方が \(\binom{N}{n}\) 通りあり，それらの符号の定め方が \(2^n\) 通りあります．これらに次の値をかければよいです：
- \(\sum_i x_i \leq K\) であるような正整数の組 \((x_1,\ldots, x_n)\) すべてに対する，\((1+K-\sum_{i}x_i)\) の総和．
これは次のような数え上げと等しいです．
- \(a + \sum x_i \leq K + 1\) となる正整数の組 \((a, x_1,\ldots, x_n)\) の個数．
- \(a + b + \sum x_i = K + 2\) となる正整数の組 \((a, b, x_1,\ldots, x_n)\) の個数．
この値は \(\binom{K+1}{n+1}\) に等しいので，答は
\[\sum_{n=0}^N 2^n\binom{N}{n}\binom{K+1}{n+1}\]
となります．
方法 2
\(\sum_i\lvert x_i\rvert = n\) となるような整数の組 \((x_1, \ldots, x_N)\) の個数を \(a_n\) とします．\(a_n\) の母関数 \(f(x) = \sum_{n=0}^{\infty} a_nx^n\) を考えると，
\[f(x) = (1+2x+2x^2+2x^3+\cdots)^N = \biggl(\frac{1+x}{1-x}\biggr)^N = \frac{(1+x)^N}{(1-x)^N}\]
となります．答は \((K+1)a_0 + Ka_1 + \cdots + 1\cdot a_K\) ですが，これは \(g(x) = 1 + 2x + 3x^2 + \cdots = (1-x)^{-2}\) を用いて \([x^{K}]f(x)g(x)\) と表せます．したがって答は\([x^K]\frac{(1+x)^N}{(1-x)^{N+2}}\) となります．
分子を \(\bigl((1-x)+2x\bigr)^N\) と表して二項展開すれば，「方法1」と同じ式が得られます．また分子をそのまま二項展開すれば，答が
\[\sum_{n=0}^N\binom{N}{n}\binom{K-n+N+1}{N+1}\]
であると分かり，この式からも正答を得ることができます．
いずれの場合も，必要な二項係数の計算を上手く行う（\(n\) ごとの比を計算する・区間積を計算できるデータ構造を利用するなど）ことで，\(O(N)\) 時間で答を求めることができます．
posted:
last update: