题解：P14368 [JOISC 2018] 修行 / Asceticism

· · 题解

鉴定为依托达芬。

零帧起手开推：

令 g_i={n \brace i}i! 表示把 n 个数划分为 i 段，段内单调递增，段之间不做要求的方案数，显然，抽象为球与盒子 n 个不同球放入 i 个不同盒子，放入后自动排序保证单调，盒子非空，第二类斯特林数再定序即可。

再令 f_i 表示把 n 个数划分为 i 段，段内单调递增，段之间不能合并为单调递增段的方案数，也就是答案。题目要我们求的就是 f_k。

于是 f 和 g 之间有关系式：

g_x=\sum_{i=0}^xf_i\binom{n-i}{x-i}

解释一下，因为 g 段内不做要求，所以我们可以插板，将 f_i 内部再划分成 x 段对 g_x 做贡献。有 n-i 个空隙要插 x-i 个板（多划 x-i 段），就是 \binom{n-i}{x-i}。

我们要得到 f_i，发现这玩意可以二项式反演：

f_x=\sum_{i=0}^x(-1)^{x-i}\binom{n-i}{x-i}g_i

把 g_i 展开写一下：

f_x=\sum_{i=0}^x(-1)^{x-i}\binom{n-i}{x-i}{n \brace i}i! $$f_x=\sum_{i=0}^x(-1)^{x-i}\binom{n-i}{n-x}{n \brace i}i!$$ 把第二类斯特林数按通项公式 ${n \brace k}=\sum_{i=0}^k\frac{(-1)^{k-i}i^n}{i!(k-i)!}$ 稍作展开，有： $$f_x=\sum_{i=0}^x(-1)^{x-i}\binom{n-i}{n-x}i!\sum_{j=0}^i\frac{(-1)^{i-j}j^n}{j!(i-j)!}$$ $j$ 提前，有： $$f_x=\sum_{j=0}^x(-1)^{x-j}j^n\sum_{i=j}^x\frac{i!}{(i-j)!j!}\binom{n-i}{n-x}$$ 前面先不管，我们聚焦 $\sum_{i=j}^x\frac{i!}{(i-j)!j!}\binom{n-i}{n-x}$，发现后面可以凑成组合数，于是改写为： $$\sum_{i=j}^x\binom{i}{j}\binom{n-i}{n-x}$$ 于是不会了，无耻地求助 Deepseek，然后给了个结论： $$\sum_{j=0}^{m}\binom{j}{a}\binom{m-j}{b}=\binom{m+1}{a+b+1}$$ ？！ 抽象一下，我们要在 $m+1$ 个数 $0,1,\dots,m$ 中选 $a+b+1$ 个数，假设先选一个 $j$，前面 $j$ 个数 $0,1,\dots,j-1$ 里要选 $a$ 个，后面 $m-j$ 个数里要选 $b$ 个，组合起来就是 $\binom{j}{a}\binom{m-j}{b}$。 然后就很简单了，令 $m=n$，$a=j$，$b=n-x$，这个式子可化为 $\binom{n+1}{n-x+j+1}$ 改写一下就是 $\binom{n+1}{x-j}

带回原式可得：

f_x=\sum_{j=0}^x(-1)^{x-j}j^n\binom{n+1}{x-j}

要求 f_k，j 太不好看了，改成 i。最终式子就是：

f_k=\sum_{i=0}^k(-1)^{k-i}i^n\binom{n+1}{k-i}

预处理阶乘及逆元，写个快速幂，O(k \log n) 计算即可。

等等，这玩意有个名字叫欧拉数？！

我*&^$#@%^……

做了整整一个上午都没做出来啊！（骗你的，刚到二项式反演就不会了）

Code:

#include<bits/stdc++.h>
#define int  long long
using namespace std;
const int mod=1e9+7;
int ksm(int a,int p){
    if(p==0)return 1;
    int tmp=ksm(a,p/2);
    if(p&1)return tmp*tmp%mod*a%mod;
    else return tmp*tmp%mod;
}
int n,k;
int fac[100005],inv[100005];
int C(int n,int m){
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
    fac[0]=inv[0]=1;
    for(int i=1;i<=100001;i++)fac[i]=fac[i-1]*i%mod,inv[i]=ksm(fac[i],mod-2);
    cin>>n>>k;
    int sum=0;
    for(int i=0;i<=k;i++)sum=(((sum+((k-i)&1?-1:1)*ksm(i,n)*C(n+1,k-i)%mod)%mod)%mod+mod)%mod;
    cout<<sum;
}

无聊爆了禁网水不了跑来这补一下二项式反演可行性自己推的一个证明过程。

::::info[过程] 当

g_x=\sum_{i=0}^xf_i\binom{n-i}{x-i}

已知时，要证明：

f_x=\sum_{i=0}^x(-1)^{x-i}\binom{n-i}{x-i}g_i

不妨将 g_x=\sum_{i=0}^xf_i\binom{n-i}{x-i} 代入，可得：

f_x=\sum_{i=0}^x(-1)^{x-i}\binom{n-i}{x-i}\sum_{j=0}^i f_j\binom{n-j}{i-j}

把两个组合数挪一起，有：

f_x=\sum_{i=0}^x(-1)^{x-i}\sum_{j=0}^i f_j\binom{n-j}{i-j}\binom{n-i}{x-i}

把两个组合数展开，有：

f_x=\sum_{i=0}^x(-1)^{x-i}\sum_{j=0}^i f_j\frac{(n-j)!}{(i-j)!(x-i)!(n-x)!}

瞪眼法发现 \frac{(n-j)!}{(i-j)!(x-i)!(n-x)!}=\binom{x-j}{i-j}\binom{n-j}{x-j}，非常好，现在都有 j 了：

f_x=\sum_{i=0}^x(-1)^{x-i}\sum_{j=0}^i f_j\binom{x-j}{i-j}\binom{n-j}{x-j}

我们充分发扬人类智慧，将 j 提前：

f_x=\sum_{j=0}^xf_j\binom{n-j}{x-j}\sum_{i=j}^x(-1)^{x-i}\binom{x-j}{i-j}

二项式定理有一个推论——

\sum_{k=0}^{m} (-1)^{m-k} \binom{m}{k} = \begin{cases} 1, & m = 0,\\ 0, & m > 0. \end{cases}

（画个杨辉三角就能看出来了）

现在很明朗了，代入 m=x-j,k=i-j，当且仅当 m=0 即 j=x 时这个式子非 0，其他情况不用考虑。

于是式子简化为：

f_x=f_x\binom{n-x}{x-x}(-1)^{x-x}\binom{x-x}{x-x}=f_x

得证。所以如此二项式反演可行。

因为鄙人高等数学一坨（基本上能想到的全不怎么会），只能用如此粗浅的方式证明，见谅见谅。 ::::