AT_joisc2018_d 修行 (Asceticism)

· · 题解

AT_joisc2018_d 修行

题意

求有多少个长为 N 排列 P 满足：

N-K=\sum\limits_i[P_i<P_{i+1}] 1\le K\le N\le 1e5

题解

我们可以先求至少有 N-j 个位置合法。我们把连续的 [P_i<P_{i+1}] 这相当于把 N 个数放进不同的 j 段里，容斥可得答案为：

\sum\limits_{i=1}^j\dbinom{j}{i}(-1)^{j-i}i^n

通过二项式反演求出恰好有 N-K 个位置合法的答案：

ANS=\sum\limits_{j=1}^{K}\dbinom{N-j}{N-K}(-1)^{K-j}\sum\limits_{i=1}^j\dbinom{j}{i}(-1)^{j-i}i^n

交换求和顺序：

=\sum\limits_{i=1}^K\sum\limits_{j=i}^{K}\dbinom{N-j}{N-K}\dbinom{j}{i}(-1)^{K-j}(-1)^{j-i}i^n =\sum\limits_{i=1}^K(-1)^{K-i}i^n\sum\limits_{j=i}^{K}\dbinom{N-j}{N-K}\dbinom{j}{i} =\sum\limits_{i=1}^K(-1)^{K-i}i^n\dbinom{N+1}{N-K+i+1}

其中 \sum\limits_{i=0}^{N}\dbinom{i}{a}\dbinom{N-i}{b}=\dbinom{N+1}{a+b+1} 可以理解为枚举 N+1 选 a+b+1 中第 a+1 个数的位置。

代码

int main(){
    cin>>n>>k;
    fac[0]=1;
    for(int i=1;i<=n+1;i++)fac[i]=fac[i-1]*i%mod;
    for(int i=1;i<=k;i++)ans=(ans+qpow(-1,k-i)*qpow(i,n)%mod*C(n+1,n-k+i+1)%mod+mod)%mod;
    cout<<ans<<"\n";
}