题解：AT_arc213_d [ARC213D] Minimize Inversion
dyc2022
·
·
题解
更好的阅读体验
感觉是很考验功底的组合计数题，可以说让人眼前一亮。
线性做法还没学。
我们先考虑对于一个排列 p，如何求出 f(p) 的值。
对于一个位置 i，我们只考虑 p_j < p_i 的位置和 p_i 产生的逆序对数量。
- 若我们给 p_i 乘的系数是 1，那么所有 j<i, p_j < p_i 的位置都会比 p_i 小，不产生贡献；所有 j>i, p_j < p_i 的位置都会比 p_i 小，都产生贡献。
- 若我们给 p_i 乘的系数是 -1，那么所有 j<i, p_j < p_i 的位置都会比 -p_i 大，都产生贡献；所有 j>i, p_j < p_i 的位置都会比 -p_i 大，不产生贡献。
由此我们发现一个位置 i 产生的贡献只和 p_i 取正还是取负有关。因此假设 L_i 表示 [1, i) 中 < p_i 的数字数量，R_i 表示 (i, n] 中 < p_i 的数字数量。那么要最小化最终的逆序对数，答案就是
\sum_{i = 1}^n \min(L_i, R_i)
接下来考虑求出对于所有排列，这个东西的和。
为了简化问题，我们先考虑没有固定一个位置的情况下，如何求出所有 n! 个排列的 f(p) 之和。
那么我们可以把贡献拆到数字上，对于每个数字求出它的贡献。
那么假设我们要求 i 这个数字产生的贡献。显然序列中有恰好 i 个 \le i 的数字。我们先不考虑这 i 个数字的内部顺序，那么有 \displaystyle {n \choose i} 种安排这 i 个数字位置的方案。接着我们枚举 1 \le j \le i，表示数字 i 在这 j 个数字中排名为 j。那么我们已经确定 i 的位置，<i 的数字有 (i-1)! 种可能的顺序，>i 的数字有 (n-i)! 种可能的顺序。最后，由于 i 左侧 <i 的数字有 j-1 个，右侧有 i-j 个，因此还要乘上 \min(j-1, i-j) 的系数。因此可以列出以下式子。
\sum_{i=1}^n {n \choose i} (i-1)! (n-i)! \sum_{j = 1}^n \min(j-1, i-j)
因此上式可以写成
$$
\sum_{i=1}^n {n \choose i} (i-1)! (n-i)! \left \lfloor \frac{i}{2}\right \rfloor \left \lfloor \frac{i-1}{2}\right \rfloor
$$
可以 $O(n)$ 求出。
***
接下来考虑添加了一个 $p_k = x$ 的限制怎么做。这个时候全局的贡献分成三部分：对 $k$ 产生的贡献，$i$ 对 $j$ 产生的贡献（$i, j \neq k$），$k$ 对 $i$ 产生的贡献（$i \neq k$）。
首先考虑其他数对 $k$ 位置的 $\min(L_k, R_k)$ 产生的贡献。那么我们枚举 $k$ 左侧和右侧分别有几个 $< x$ 的数字。那么 $<x$ 的数字内部共有 $(x-1)!$ 种可能的顺序，$>x$ 的数字内部共有 $(n-x)!$ 种可能的顺序，在 $k$ 左侧安排 $i$ 个 $<x$ 的数字共有 $\displaystyle{k-1 \choose i}$ 种方案，在 $k$ 右侧安排 $j$ 个 $<x$ 的数字共有 $\displaystyle{n-k \choose j}$ 种方案。因此有式子
$$
(x-1)!(n-x)! \sum_{i + j = x-1}{k-1 \choose i} {n-k \choose j} \min(i,j)
$$
接下来考虑两个不为 $k$ 的位置之间产生的贡献。容易发现这种情况就相当于没有固定任何位置下，$n' = n-1$ 的情况。因此代入上面已经推得的式子，可得
$$
\sum_{i=1}^{n-1} {n-1 \choose i} (i-1)! (n-i-1)! \left \lfloor \frac{i}{2}\right \rfloor \left \lfloor \frac{i-1}{2}\right \rfloor
$$
接下来考虑本题最为复杂的部分：$k$ 对一个位置 $l$ 的贡献。
那么如果 $k$ 的插入能对 $L_l$ 或 $R_l$ 造成影响，那么一定要保证 $x < p_l$。那么我们记 $p_l = y$。
接下来，我们对 $l$ 相对于 $k$ 的位置展开讨论。显然如果 $l<k$，那么 $k$ 的插入会让 $R_l$ 增加 $1$。如果需要让 $\min(L_l, R_l)$ 增加，需保证 $L_l > R_l$。否则若 $l>k$，那么需保证 $L_l < R_l$。接下来假设 $k$ 左侧放置了 $i$ 个 $\le y$ 的数字，右侧放置了 $j$ 个 $\le y$ 的数字，$l$ 在所有 $\le y$ 的数字（不包含 $p_k$）中排名为 $t$。
- 若 $l<k$。那么 $L_l = t-1, R_l = j + i - t$。那么由 $L_l > R_l$，因此有 $\displaystyle {t > \frac{i+j+1}{2}}$。因此，若 $i>j$，则 $l$ 有 $\displaystyle {\frac{i-j}{2}}$ 种选择方案。否则，$l$ 有 $0$ 种选择方案。
- 若 $l>k$。同理，可以得到：若 $i < j$，则 $l$ 有 $\displaystyle {\frac{j-i}{2}}$。否则 $l$ 有 $0$ 种选择方案。
又因为安排 $< y$ 且 $\neq x$ 的数字总共有 $(y-2)!$ 种顺序，$> y$ 的数字有 $(n-y)!$ 种顺序。因此可以列出式子：
$$
add_y = (y-2)!(n-y)! \sum_{i+j = y-1} \left \lfloor \frac{\left| i - j \right|}{2} \right \rfloor {k-1 \choose i} {n-k \choose j}
$$
现在考虑第一部分和第三部分的式子要怎么快速求出。
先考虑 $add_y$ 的求法。注意到，$|i - j| = i + j - 2 \cdot \min(i, j) = y - 1 - 2 \cdot \min(i, j)$。因此这个式子可以改写为
$$
add_y = (y-2)!(n-y)! \sum_{i+j = y-1} \left (\left \lfloor \frac{y - 1}{2} \right \rfloor - \min(i, j)\right ){k-1 \choose i} {n-k \choose j}
$$
接下来只需要考虑快速求出以下两个式子的值：
$$
\sum_{i +j = C} {k - 1 \choose i} {n - k \choose j} \\
\sum_{i + j = C}{k - 1 \choose i}{n - k \choose j} \min(i, j)
$$
第一个式子是范德蒙德卷积，容易得到取值为 $\displaystyle{n - 1 \choose C}$。
第二个式子可以分治 NTT 求解。具体得，我们不妨先假设 $i<j$，那么就可以看作是 $\displaystyle{{k - 1 \choose i} \cdot i}$ 和 $\displaystyle{n-k \choose j}$ 这两个函数卷积，其中要求 $i < j$。至于 $i>j$ 的情况，倒过来重复这一过程即可。
最后，一个 $y$ 会对所有 $<y$ 的 $x$ 产生 $add_y$ 的贡献。这个用差分轻松维护。
那么这道题就做完了，时间复杂度为 $O(n \log^2 n)$。存在线性做法，但是我不会。
```cpp
#include<bits/stdc++.h>
#define endl '\n'
#define N 525006
using namespace std;
using poly=vector<int>;
constexpr int MOD=998244353,G=3,invG=332748118;
int r[N];
int qpow(int x,int y)
{
int ret=1;
for(;y;y>>=1,x=1ll*x*x%MOD)if(y&1)ret=1ll*ret*x%MOD;
return ret;
}
void NTT(poly &a,int opt)
{
int len=a.size();
for(int i=0;i<len;i++)
if(i<r[i])swap(a[i],a[r[i]]);
for(int i=1;i<len;i<<=1)
{
int tmp=i<<1,Wn=qpow(opt==1?G:invG,(MOD-1)/tmp);
for(int j=0;j<len;j+=tmp)
{
int w=1,x,y;
for(int k=0;k<i;k++,w=1ll*w*Wn%MOD)
{
x=a[j+k],y=1ll*w*a[i+j+k]%MOD;
a[j+k]=(x+y)%MOD,a[i+j+k]=(x+MOD-y)%MOD;
}
}
}
}
poly operator +(poly a,poly b)
{
int n=a.size(),m=b.size();
poly ans(max(n,m));
for(int i=0;i<max(n,m);i++)
{
ans[i]=0;
if(i<n)ans[i]=(ans[i]+a[i])%MOD;
if(i<m)ans[i]=(ans[i]+b[i])%MOD;
}
return ans;
}
poly operator *(poly a,poly b)
{
int n=a.size(),m=b.size(),len=1,lg=0;
while(len<n+m)len<<=1,lg++;
while(a.size()<len)a.push_back(0);
while(b.size()<len)b.push_back(0);
for(int i=0;i<len;i++)
r[i]=(r[i>>1]>>1)|((i&1)<<lg-1);
NTT(a,1),NTT(b,1);
for(int i=0;i<len;i++)a[i]=1ll*a[i]*b[i]%MOD;
NTT(a,-1);
int inv=qpow(len,MOD-2);
poly ans(n+m-1);
for(int i=0;i<n+m-1;i++)ans[i]=1ll*a[i]*inv%MOD;
return ans;
}
poly& operator +=(poly &a,poly b) {return a=a+b;}
poly& operator *=(poly &a,poly b) {return a=a*b;}
int n,k,fac[N],ifac[N],ans[N],h[N];
poly f,g,res;
inline void add(int &x,int y) {x+=y,x-=x>=MOD?MOD:0;}
inline void dec(int &x,int y) {x+=MOD-y,x-=x>=MOD?MOD:0;}
int binom(int x,int y) {return x<y?0:1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;}
void solve(int l,int r)
{
if(l==r)return;
int mid=l+r>>1;
poly x(mid-l+1),y(r-mid);
for(int i=l;i<=mid;i++)x[i-l]=f[i];
for(int i=mid+1;i<=r;i++)y[i-mid-1]=g[i];
x*=y; int sz=x.size();
for(int i=0;i<sz;i++)
if(l+mid+1+i<=n)add(res[l+mid+1+i],x[i]);
solve(l,mid),solve(mid+1,r);
}
main()
{
scanf("%d%d",&n,&k),fac[0]=1;
for(int i=1;i<N;i++)fac[i]=1ll*i*fac[i-1]%MOD;
ifac[N-1]=qpow(fac[N-1],MOD-2);
for(int i=N-2;~i;i--)ifac[i]=1ll*(i+1)*ifac[i+1]%MOD;
f.resize(n+1),g.resize(n+1),res.resize(n+1);
for(int &i:res)i=0;
for(int i=0;i<=n;i++)f[i]=1ll*i*binom(k-1,i)%MOD;
for(int i=0;i<=n;i++)g[i]=binom(n-k,i);
solve(0,n);
for(int i=0;i<=n;i++)f[i]=1ll*i*binom(n-k,i)%MOD;
for(int i=0;i<=n;i++)g[i]=binom(k-1,i);
solve(0,n);
for(int i=0;i*2<=n;i++)
add(res[i*2],1ll*binom(k-1,i)*binom(n-k,i)%MOD*i%MOD);
for(int i=1;i<=n;i++)
ans[i]=1ll*fac[i-1]*fac[n-i]%MOD*res[i-1]%MOD;
int all=0;
for(int i=1;i<n;i++)
{
int coef=1ll*binom(n-1,i)*fac[i-1]%MOD*fac[n-i-1]%MOD;
coef=1ll*coef*(i>>1)%MOD;
coef=1ll*coef*(i-1>>1)%MOD;
add(all,coef);
}
for(int i=1;i<=n;i++)add(ans[i],all);
for(int i=1;i<=n;i++)
{
int coef=1ll*(i-1>>1)*binom(n-1,i-1)%MOD;
dec(coef,res[i-1]%MOD);
coef=1ll*coef*fac[i-2]%MOD*fac[n-i]%MOD;
add(h[1],coef),dec(h[i],coef);
}
for(int i=1;i<=n;i++)add(h[i],h[i-1]);
for(int i=1;i<=n;i++)
printf("%d\n",(ans[i]+h[i])%MOD);
return 0;
}
```