在处理组合数的时候，我们经常能够遇到形如：
f ( n ) = ∑ i = 0 n ( n i ) g ( i ) f(n) = \sum_{i=0}^n \binom{n}{i} g(i) f(n)=i=0∑n(in)g(i)
我们想反过来求 g ( n ) g(n) g(n) 考虑 f f f 的 EGF 为 F ( x ) F(x) F(x) 而 g g g 的 EGF 为 G ( x ) G(x) G(x) 。并且 C ( x ) = ∑ n ≥ 0 x n n ! = e x C(x) = \sum_{n \ge 0} \frac{x^n}{n!} = e^x C(x)=∑n≥0n!xn=ex 那么：
F ( x ) = C ( x ) G ( x ) = e x G ( x ) F(x) = C(x)G(x) = e^xG(x) F(x)=C(x)G(x)=exG(x)
那么 G ( x ) = F ( x ) e − x G(x) = F(x) e^{-x} G(x)=F(x)e−x ，再次展开得到：
g ( n ) = ∑ i = 0 n ( n i ) ( − 1 ) n − i f ( i ) g(n) = \sum_{i = 0}^n \binom{n}{i} (-1)^{n-i}f(i) g(n)=i=0∑n(in)(−1)n−if(i)
上述过程为二项式反演。
另外，二项式反演还有另外一种形式：
f ( n ) = ∑ i ≥ n ( i n ) g ( i ) ⇔ g ( n ) = ∑ i ≥ n ( i n ) f ( i ) ( − 1 ) i − n f(n) = \sum_{i \ge n} \binom{i}{n} g(i) \Leftrightarrow g(n) = \sum_{i \ge n} \binom{i}{n} f(i) (-1)^{i-n} f(n)=i≥n∑(ni)g(i)⇔g(n)=i≥n∑(ni)f(i)(−1)i−n
我们对于固定的 n n n ，求出 S ( n , m ) S(n,m) S(n,m) 。
考虑引理：
m
n
=
∑
i
=
0
m
{
n
i
}
×
i
!
×
(
m
i
)
m^n=\displaystyle \sum _{i=0}^{m}
左边是把 n n n 个物品随机放入 m m m 个箱子中，右边 i i i 是枚举非空箱子的个数，我们将 n n n 个物品分成 i i i 个集合塞到 i i i 个非空的箱子中。
m
n
+
1
=
∑
i
=
0
m
{
n
i
}
×
i
!
×
(
m
i
)
m^n + 1=\displaystyle \sum _{i=0}^{m}
经过二项式反演可得：
{
n
m
}
m
!
=
∑
i
=
0
m
(
−
1
)
m
−
i
(
m
i
)
i
n
化简可得：
{
n
m
}
=
∑
i
=
0
m
(
−
1
)
m
−
i
(
m
−
i
)
!
×
i
n
i
!
直接使用 NTT 卷积可做。
首先设至少在对于所有任意的 k k k 个位置上有“bit”的方案数为 f ( k ) f(k) f(k) 并且设答案为 g ( k ) g(k) g(k) 那么有：
f ( k ) = ∑ j ≥ k ( j k ) g ( j ) f(k) = \sum_{j \ge k} \binom{j}{k} g(j) f(k)=j≥k∑(kj)g(j)
其中 f ( k ) = ( n − 2 k k ) 2 6 n − 3 k f(k) = \binom{n-2k}{k}26^{n-3k} f(k)=(kn−2k)26n−3k 。
对上面的式子进行二项式反演得到：
∑ j ≥ k ( − 1 ) j − k ( j k ) f ( j ) = g ( k ) \sum_{j \ge k}(-1)^{j-k} \binom{j}{k} f(j) = g(k) j≥k∑(−1)j−k(kj)f(j)=g(k)
变形得到：
∑ j ≥ k ( − 1 ) j − k j ! ( j − k ) ! f ( j ) = g ( k ) k ! \sum_{j \ge k}(-1)^{j-k} \frac{j!}{(j-k)!} f(j) = g(k)k! j≥k∑(−1)j−k(j−k)!j!f(j)=g(k)k!
设 P ( x ) = ∑ n ( − 1 ) − n 1 ( − n ) ! x n P(x) = \sum_{n} (-1)^{-n} \frac{1}{(-n)!} x^n P(x)=∑n(−1)−n(−n)!1xn 而 Q ( x ) = ∑ n n ! f ( n ) x n Q(x) = \sum_{n} n!f(n) x^n Q(x)=∑nn!f(n)xn 。
最后计算 P × Q P \times Q P×Q 即可。