文章

· · 个人记录

浅谈信息学竞赛数学——斯特林数

FFT

高斯消元

多点插值

容斥原理

子集dp

x^{\overline{n}} = x(x + 1)...(x + n - 1) x^{\underline{n}} = x(x - 1)...(x - n + 1) change: x^{\overline{n}} = (x + n - 1)^{\overline{n}}

我们假设f[n][k]表示n个点划分成k个环的方案数.

一般用中括号表示.

那么递推公式就是：

f[n][k] = f[n - 1][k - 1] + (n - 1)f[n - 1][k]. f[n][k] = \sum_{i = 1}^{n} \times C_{n - 1}^{i - 1} \times (i - 1)! f[n - i][k - 1]

所以可得:x^{\overline{n}} = \sum_{i = 0}^{n}f[n][i] \times x^i

现在有一个显然的问题，如何快速的求出f[n][i]?

可以使用较为暴力的分治FFT复杂度O(nlog^2n)

同时我们也可以使用倍增FFT

考虑倍数关系递推：x^{\overline {2n}} = x^{\overline n} \times (x + n)^{\overline n}

两者都是关于x的n阶多项式，后者可以由前者得到。

复杂度O(nlogn)

我们假设f[n][k]表示n个点划分成k个集合的方案数.

一般用花括号表示.

那么递推公式就是：

f[n][k] = f[n - 1][k - 1] + k \times f[n - 1][k]. f[n][k] = \sum_{i = 1}^{n} \times C_{n - 1}^{i - 1} \times f[n - i][k - 1] x^n = \sum_{i = 0}^{n} f[n][i] \times x^{\underline i} x^n = \sum_{i = 0}^{x}C_{x}^{i} \times i! \times

考虑二项式反演：

x! \times f[n][x] = \sum_{i = 0}^{x} (-1)^{(x - i)} C_{x}^{i} \times i^n 举个小例子： $n$个带标号的球放到$m$个无标号的盒子，不能有空盒的方案数？ 如果划分给有标号的，那么在乘上$m!$即可。 - 小技巧 求$(\sum_{i = 1}^{n} c_i)^m

考虑某k个x组成的系数和。

\sum_{\sum a_i = m} {m! \over \prod a_i!} = S_{m,k} \times k!

表示m个物品放到k个带标号的方案数。

当x_i取0或1的时候，可以考虑若某k个x_i都为1，对答案就有上述贡献。

x^{n} = \sum{i = 0}^{n}S_{n,i} x^{\underline{i}}

二项式反演可得：

(-1)^n \times x^n = \sum_{i = 0}^{n} S_{n,i} (-1)^{n - i} \times (-1)^i x^{\underline{i}}

除过去就是：x^n = \sum_{i = 0}^{n} S_{n,i} (-1)^{n - i} x^{\overline{i}}

相像的是：x^{\underline{n}} = \sum{i = 0}^{n} S_{n,i} (-1)^{n - i} \times x^i

题目大意：

求一个函数的值。

f(n) = \sum_{i = 0}^{n} \sum_{j = 0}^{i} S_{i,j} \times 2^j \times j! $n<=100000

乍一看到就是应该就是一个O(nlogn)的复杂度...

S$就是把$i$个数划分成$j$个集合的方案数再乘上$2^j \times j!

考虑后面转化一下。

设f[i] = \sum{j = 0}^{i}S_{i,j} \times 2^j \times j! = \sum{j = 1}^{i}C_{i}^{j} \times 2f[i - j]

然后多项式求逆即可QwQ，如果不会多项式求逆，也可以搞分治FFT

题目大意：

给定一棵树，对于每一个点，输出\sum{j = 1}^{n} dis(i,j)^m

n<=50000,m<=500

考虑dp，设dp[u]表示u子树内的点到u的答案。

首先使用dfs更新一遍求出一号点的答案，然后再次dfs求得每个点的答案。

真顺畅...啊？

发现不好不好求\sum(d + 1)^m的答案。

就考虑在已知\sum d^m的答案下如何求上式。

首先求得d的每一个次方i (0<=i<=m)

(d + 1)^m = \sum_{i = 0}^{m} C_{m}^{i} d^i

原理为二项式定理。

这样就可以50了。

发现瓶颈就是在求+1的这一个上面，我们考虑对于每一个i(0<=i<=m)维护\sum d^{\underline{i}}

所以：(d + 1)^{\underline{m}} = (d + 1) \times d^{\underline{m - 1}} = (d - m + 1) \times d^{\underline{m - 1}} + m \times d^{\underline{m - 1}} = d^{\underline{m}} + m \times d^{\underline{m - 1}}

然后套用上述二类斯特林数中给定的第一个式子即可在m的时间内算完。

复杂度O(nm) ，期望得分:100.

有一个k面的骰子，扔n次，设cnt_i表示i出现的次数，求所有方案中：

\prod{i = 1}^{L} cnt_i ^ {F} n,k <= 10^9,F<=1000,F \times L <= 50000

设f[i][j]表示第i次是否扔出了j，要求的就是:

\prod_{i = 1}^{L} (\sum_{j = 1}^{n} f[j][i])^F

对于每一个i,如果有k个f[j][i]是1，那么就有S_{F,k} k!的贡献

要求的其实就是到底有多少个1，由于互相不独立，满足每行只有1个1，所以dp一下做个背包即可。

背包容量只需要2003即可，因为n^{\underline{2003}} = 0 mod 2003

加上倍增FFT即可通过。

推荐题目：UOJ_如何优雅的求和,小C的岛屿.