LOJ#6077. 「2017 山东一轮集训 Day7」逆序对

生成函数 + DP ，或者容斥，一道好题。

下面皆视 $n,k$ 同阶。

生成函数 $\mathcal{O}(k\sqrt{k})$

首先根据题意，得到答案得生成函数：

$$F(x)=\prod _{i=1}^n(\sum _{j=0}^{i-1}{x}^j)=\prod _{i=1}^n\frac{(1-x^i)}{1-x}=\frac{1}{(1-x{)}^n}\prod _{i=1}^n(1-x^i)$$

前面一部分是简单的，我们有 ${\displaystyle \frac{1}{(1-x{)}^n}=\sum _{i\ge 0}(\genfrac{}{}{0ex}{}{n+i-1}{i})x^i}$。于是考虑分子即可，注意到我们最多只会选出 $\mathcal{O}(\sqrt{k})$ 个 $-x^i$。再利用好每个 $-x^i$ 仅能选择一次这一点，我们进行 DP。设 $f(i,j)$ 表示选择了 $i$ 个，其和为 $j$ 的方案数。我们考虑两种转移：

1. 前 $i$ 个数全部 $+1$： $f(i,j)\leftarrow f(i,j-i)$。
2. 前 $i-1$ 全部 $+1$，插入一个新的 $1$：$f(i,j)\leftarrow f(i-1,j-i)$。

需要注意的是，若 $k>n$ ，那么其中的数可能会大于 $n$，我们减掉这一部分的答案即可。

1. 若 $j>n$，$f(i,j)\leftarrow -f(i-1,j-n-1)$。

DP 之后在乘上系数即可，时间复杂度 $\mathcal{O}(k\sqrt{k})$。

容斥 $\mathcal{O}(k\sqrt{k})$

有 $n$ 个数 $x_i$ 满足限制条件 $x_i\in [0,i-1]$，现在求满足 ${\displaystyle \sum _{i=1}^n{x}_i=k}$ 的 方案数。

真正限制我们的是 $x_i\in [0,i-1]$ 这一条件，我们考虑容斥去掉。钦定 $j\in S$ 中 $x_j$ 满足 $x_j\ge j$，我们将这些 $x_j$ 减去 $j$，那么所有的限制就变成了 $x_i\ge 0$，使用插板法即可直接算出答案。

现在我们相当于求从 $1,2,\cdots ,i-1,i$ 选出若干个，使其和为 $j$。问题转化为与上面一模一样的 DP！！！这样时间复杂度也是 $\mathcal{O}(k\sqrt{k})$。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e5+10,M=500+10,mod=1e9+7;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m,k;
int f[M][N];
int fac[N<<1],ifac[N<<1];

inline int adj(int x){return x>=mod?x-mod:x;}
inline int qpow(int x,int k=mod-2)
{
    int res=1;
    while(k)
    {
        if(k&1)res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return res;
}
inline void init(int n)
{
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n]);
    for(int i=n;i;i--)ifac[i-1]=1ll*ifac[i]*i%mod;
}
inline int C(int n,int m)
{
    if(m>n)return 0;
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
    read(n,k);
    init(n+k);
    m=sqrt(k<<1)+1;
    f[0][0]=1;
    for(int i=1;i<=m;i++)
        for(int j=i;j<=k;j++)
            f[i][j]=adj(adj(f[i][j-i]+f[i-1][j-i])+((j>n)?(mod-f[i-1][j-n-1]):0));
    int ans=0;
    for(int i=0;i<=k;i++)
    {
        int res=0;
        for(int j=0;j<=m;j++)
            res=adj(res+((j&1)?(mod-f[j][k-i]):f[j][k-i]));
        ans=adj(ans+1ll*C(n+i-1,i)*res%mod);
    }
    printf("%d\n",ans);
    return 0;
}

能不能再给力一点？

生成函数 + 多项式 exp $\mathcal{O}(n\log n)$

我们还是写出其生成函数：

$$F(x)=\frac{1}{(1-x{)}^n}\prod _{i=1}^n(1-x^i)$$

前一部分还是一样，我们有 ${\displaystyle \frac{1}{(1-x{)}^n}=\sum _{i\ge 0}(\genfrac{}{}{0ex}{}{n+i-1}{i})x^i}$。考虑后一部分，利用 P4389 付公主的背包 一样的技巧，先对其取 $\ln$ 将其转化为加法。我们有下面的式子：

$$\ln (1-x^k)=-\sum _{i>0}\frac{1}{i}{x}^{ik}$$

这个式子可以通过泰勒展开得到，当然也可以通过对两边求导得到。

所以我们得到：

$$\ln (\prod _{i=1}^n(1-x^i))=-\sum _{i=1}^n\sum _{j>0}\frac{1}{j}{x}^{ij}$$

右边暴力 $\mathcal{O}(n\ln n)$ 枚举，再做一次多项式 $\exp$ 即可，最后乘上 ${\displaystyle \frac{1}{(1-x{)}^n}=\sum _{i\ge 0}(\genfrac{}{}{0ex}{}{n+i-1}{i})x^i}$ 即可。时间复杂度为 $\mathcal{O}(n\log n)$。需要用到任意模数 NTT。