题解：P7781 「MCOI-Zero / AC6-M07」Selumna Peak
__yhz
·
·
题解
200 紫 AC。
先考虑求出 ans_n。
考虑每一对 i<j 的 (a_i,a_j) 的贡献，有 6 种情况：
下面每一行依次对应前面的描述。
\begin{aligned}
ans_n=
&\sum_{i=1}^n
\sum_{j=i+1}^n
\sum_{k=2}^n
{n-2\choose k-2}
\frac{k!}2
\\+&
\sum_{i=1}^n
\sum_{j=i+1}^n
[a_i>a_j]
\sum_{k=0}^{n-2}
{n-2\choose k}
k!
\\+&
\sum_{i=1}^n
\sum_{j=i+1}^n
[a_i>a_j]
\sum_{k=1}^{n-1}
\sum_{l=1}^{k}
{j-2\choose l-1}
{n-j\choose k-l}
\ l\
(k-1)!
\\+&
\sum_{i=1}^n
\sum_{j=i+1}^n
[a_i>a_j]
\sum_{k=1}^{n-1}
\sum_{l=1}^{k}
{i-1\choose k-l}
{n-i-1\choose l-1}
\ l\
(k-1)!
\\+&
\sum_{i=1}^n
\sum_{j=i+1}^n
[a_i<a_j]
\sum_{k=2}^{n-1}
\sum_{l=1}^{k-1}
{j-2\choose k-l-1}
{n-j\choose l}
\ l\
(k-1)!
\\+&
\sum_{i=1}^n
\sum_{j=i+1}^n
[a_i<a_j]
\sum_{k=2}^{n-1}
\sum_{l=1}^{k-1}
{i-1\choose l}
{n-i-1\choose k-l-1}
\ l\
(k-1)!
\end{aligned}
考虑化简。
对于第一行，我们发现 i,j 并没有用，直接化为 n(n-1)/2。
对于第二行，我们可以把 k 放到前面。
中间两行似乎不太好化简的样子。
对于最后两行：
先根据
{x\choose y}y=x{x-1\choose y-1}
把 l 放到组合数里，换出一个只含 i 或 j 的式子，提到前面去。
再将 (k-1)! 放到前面去，发现 l 的部分构成范德蒙德卷积。
\begin{aligned}
\\&
\sum_{k=2}^{n-1}
\sum_{l=1}^{k-1}
{j-2\choose k-l-1}
{n-j\choose l}
\ l\
(k-1)!
+
\sum_{k=2}^{n-1}
\sum_{l=1}^{k-1}
{i-1\choose l}
{n-i-1\choose k-l-1}
\ l\
(k-1)!
\\
=&
(n-j)
\sum_{k=2}^{n-1}
\sum_{l=1}^{k-1}
{j-2\choose k-l-1}
{n-j-1\choose l-1}
(k-1)!
+
(i-1)
\sum_{k=2}^{n-1}
\sum_{l=1}^{k-1}
{i-2\choose l-1}
{n-i-1\choose k-l-1}
(k-1)!
\\
=&
(n-j)
\sum_{k=2}^{n-1}
(k-1)!
{n-3\choose k-2}
+
(i-1)
\sum_{k=2}^{n-1}
(k-1)!
{n-3\choose k-2}
\\
=&
(n-j+i-1)
\sum_{k=2}^{n-1}
(k-1)!
{n-3\choose k-2}
\end{aligned}
既然最后两行化简了，那么我们就可以容斥一下，总方案减去不满足的情况（就是最后两行），从而化简了中间两行。
化简结果：（对应前面的第一行，第二行，中间两行，最后两行）
\begin{aligned}
ans_n=
&\frac{n(n-1)}4
\sum_{k=0}^{n-2}
{n-2\choose k}
(k+2)!
\\+&
\sum_{k=0}^{n-2}
{n-2\choose k}
k!
\sum_{i=1}^n
\sum_{j=i+1}^n
[a_i>a_j]
\\+&
\sum_{i=1}^n
\sum_{j=i+1}^n
[a_i>a_j]
\left(
2
\sum_{k=0}^{n-2}
(k+1)!
{n-2\choose k}
-(n-j+i-1)
\sum_{k=0}^{n-3}
(k+1)!
{n-3\choose k}
\right)
\\+&
\sum_{i=1}^n
\sum_{j=i+1}^n
[a_i<a_j]
(n-j+i-1)
\sum_{k=0}^{n-3}
(k+1)!
{n-3\choose k}
\end{aligned}
这个式子里有许多类似的结构，可以把它们拿出来。
设：
\begin{aligned}
f_x&=\sum_{k=0}^{x}k!{x\choose k}
=\sum_{k=0}^{x}x^{\underline{k}}
\\
g_x&=\sum_{k=0}^{x}(k+1)!{x\choose k}
=\sum_{k=0}^{x}(k+1)x^{\underline{k}}
\\
h_x&=\sum_{k=0}^{x}(k+2)!{x\choose k}
=\sum_{k=0}^{x}(k+1)(k+2)x^{\underline{k}}
\end{aligned}
它们都有递推式。
\begin{aligned}
f_x&=1+nf_{n-1}
\\
g_x&=f_x+xg_{x-1}
\\
h_x&=2g_x+xh_{x-1}
\end{aligned}
替换后得到
\begin{aligned}
ans_n=
&\frac{n(n-1)}4
h_{n-2}
\\+&
f_{n-2}
\sum_{i=1}^n
\sum_{j=i+1}^n
[a_i>a_j]
\\+&
\sum_{i=1}^n
\sum_{j=i+1}^n
[a_i>a_j]
\left(
2g_{n-2}-(n-j+i-1)g_{n-3}
\right)
\\+&
\sum_{i=1}^n
\sum_{j=i+1}^n
[a_i<a_j]
(n-j+i-1)g_{n-3}
\end{aligned}
设 I_n 表示 a_1\sim a_n 的逆序对数，S_n 表示 a_1\sim a_n 的逆序对的 n-j+i-1 贡献和。通过树状数组可以 O(\log n) 求出。
\begin{aligned}
ans_n=
&\frac{n(n-1)}4 h_{n-2}+I_nf_{n-2}+2I_ng_{n-2}
\\&-
\sum_{i=1}^n
\sum_{j=i+1}^n
[a_i>a_j]
(n-j+i-1)g_{n-3}
\\&+
\sum_{i=1}^n
\sum_{j=i+1}^n
[a_i<a_j]
(n-j+i-1)g_{n-3}
\\=
&\frac{n(n-1)}4 h_{n-2}+I_nf_{n-2}+2I_ng_{n-2}
\\&-
2S_ng_{n-3}
+
\sum_{i=1}^n
\sum_{j=i+1}^n
(n-j+i-1)g_{n-3}
\end{aligned}
对于 \sum_{i=1}^n\sum_{j=i+1}^n(n-j+i-1)：
\begin{aligned}
&\quad\sum_{i=1}^n\sum_{j=i+1}^n(n-j+i-1)
\\&=\sum_{i=1}^n\sum_{j=i+1}^n(n-j)+\sum_{i=1}^n\sum_{j=i+1}^n(i-1)
\\&=\sum_{j=1}^n(j-1)(n-j)+\sum_{i=1}^n(n-j)(i-1)
\\&=2\sum_{i=1}^n(n-j)(i-1)
\\&=2\left(-\sum_{i=1}^ni^2+(n-1)\sum_{i=1}^ni-n^2\right)
\end{aligned}
最终总复杂度为 $O(n\log n)$。
:::info[代码]
```cpp
#include <bits/stdc++.h>
#define ll long long
#define F(i,l,r) for(ll i=l;i<=r;i++)
using namespace std;const ll A=1e6+5,_=20051131;
ll rd(){ll x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c))x=x*10+c-'0',c=getchar();return x*f;}
ll n,a[A],f[A],g[A],h[A],ii[A],d[A],c[A],S[A],e[A];
ll chk(ll n){
ll s=h[n-2]*10025566%_*(n*(n-1)/2%_)%_;
s=(s+ii[n]*f[n-2]+2*ii[n]*g[n-2])%_;
s=(s+(-e[n]+n*(n+1)/2*(n+1)-n*n)%_*2*g[n-3])%_;
s=(s-2*(n-1)*ii[n]%_*g[n-3]%_+2*S[n]*g[n-3]%_+_)%_;
return s;
}
int main(){n=rd();
F(i,1,n){ll x=rd();a[i]=x;
ll z=i-1;
for(ll j=x;j;j-=(j&-j))z-=d[j];
for(ll j=x;j<=n;j+=(j&-j))d[j]++;
ii[i]=ii[i-1]+z;
S[i]=S[i-1]-(i-1)*i/2+z*i;
for(ll j=x;j;j-=(j&-j))S[i]+=c[j];
for(ll j=x;j<=n;j+=(j&-j))c[j]+=i;
ii[i]=(ii[i]%_+_)%_;
S[i]=(S[i]%_+_)%_;
}
f[0]=g[0]=1,h[0]=2;
F(i,1,n)f[i]=(1+i*f[i-1])%_,
g[i]=(f[i]+i*g[i-1])%_,
h[i]=(2*g[i]+i*h[i-1])%_,
e[i]=e[i-1]+i*i;
F(i,1,n)cout<<(chk(i)+f[i]*(ii[n]-ii[i]+_))%_<<"\n";
return 0;
}
```
:::
码字不易点个赞再走吧。