AT_joisc2018_d 修行
题意
N−K=i∑[Pi<Pi+1]
1≤K≤N≤1e5
题解
我们可以先求至少有
N−j 个位置合法。我们把连续的
[Pi<Pi+1] 这相当于把
N 个数放进不同的
j 段里，容斥可得答案为：
i=1∑j(ij)(−1)j−iin
通过二项式反演求出恰好有
N−K 个位置合法的答案：
ANS=j=1∑K(N−KN−j)(−1)K−ji=1∑j(ij)(−1)j−iin
交换求和顺序：
=i=1∑Kj=i∑K(N−KN−j)(ij)(−1)K−j(−1)j−iin
=i=1∑K(−1)K−iinj=i∑K(N−KN−j)(ij)
=i=1∑K(−1)K−iin(N−K+i+1N+1)
其中
i=0∑N(ai)(bN−i)=(a+b+1N+1) 可以理解为枚举
N+1 选
a+b+1 中第
a+1 个数的位置。
代码
CPPint 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";
}