loj6077. 「2017 山东一轮集训 Day7」逆序对 记录

· · 个人记录

由于你是\text{YK}，你会有限微积分上硬套一个高斯消元，于是你开始考虑多项式解法

由于你听了\text{zhm}一句话

注意到每次添加一个数 a_i ，必然增加逆序对数量 c_i ，其中 c_i\in[0,i-1]

于是你 一眼 出来如果给定一个序列 c_{[1,n]} ，则必然能复原出一个 a_{[1,n]} ，他们是一一对应的

所以你就开始思考，就相当于解一个方程，问方程有几个解

其中方程是

\sum_{i=1}^nc_i=k \ \ \ \ \ \ \ \ \ \ \ \ c_i\in[0,i-1]∩\text{N}^*

于是你一眼看出来这是一个母函数优化，对于每个 c_i 表示为 (1+x+x^2+\ldots+x^{i-1})

把每个 c_i 对应的母函数相乘，他的 x^k 项就是方案数，物理意义上极其容易理解，所以你随便上一个有限微积分就把式子化完了

ans=[x^k]\frac{\prod_{i=1}^n(x^i-1)}{(x-1)^n}

套一个任意模数多项式乘法，任意模数多项式乘法逆，任意模数多项式分治乘法，任意模数多项式乘法快速幂就行了，可以做到 O(n\log^2n)

或者你可以把他 \ln 了，再 \exp 了，随意上一个有限偏导后类微分调和即可

现在是 20:52 ，我看我什么时候写完

现在是 21:22 ，我写完了

#include<bits/stdc++.h>
using namespace std;
const int p=1e9+7;
void add(int &a,int b){
    a+=b;(a>=p)&&(a-=p);
}
void sub(int &a,int b){
    a-=b;(a<0)&&(a+=p);
}
int n,k,m;
int f[900][100010];
struct CC{
    int n,p,jc[200010],jcinv[200010];
    int ksm(int a,int b){
        int ans=1;for(;b;b>>=1,a=(long long)a*a%p)
        if(b&1)ans=(long long)ans*a%p;return ans;
    }
    void init(int nn,int pp){
        n=nn;p=pp;jc[0]=1;for(long long i=1;i<=n;i++)jc[i]=jc[i-1]*i%p;
        jcinv[n]=ksm(jc[n],p-2);for(long long i=n-1;~i;i--)jcinv[i]=jcinv[i+1]*(i+1)%p;
    }
    int C(int n,int m){return (long long)jc[n]*jcinv[m]%p*jcinv[n-m]%p;}
}st;
signed main(){
    cin>>n>>k;
    m=sqrt(n*2)*2;
    f[0][0]=1;
    for(int j=1;j<=m;j++)
        for(int i=j;i<=k;i++){
            add(f[j][i],f[j][i-j]);
            add(f[j][i],f[j-1][i-j]);
            if(i>n)add(f[j][i],p-f[j-1][i-n-1]);
        }
    st.init(n+k,p);
    int ans=0;
    for(int i=0;i<=k;i++){
        int res=0;
        for(int j=0;j<=m;j++)
        if(j&1)sub(res,f[j][i]);
        else add(res,f[j][i]);
        add(ans,(long long)res*st.C(k-i+n-1,n-1)%p);
    }
    cout<<ans;
}

为了防止本博文太神必，我在简要说说代码

你发现 \text{MTT} 常数几乎可以看做一只 \log ，3\log 不过 1e5 ，于是你毅然弃疗。

注意到背包本质是一个生成函数，于是你使用背包，却发现开不下 kn 数组。

于是你思考策略，你 一眼 发现了一个自然根号，就是构成 k 的 c_i 不超过 O(\sqrt k)个，于是你使用 f_{i,j} 表示为了构成 j ，使用了 i 个数，因为直接背包很难，你要不时考虑如何上有限微积分干他表示状态，于是你决定这 i 个数可以重复，于是你就容斥了

处理答案时你随便乘上组合数，都是常规操作，于是你做出了一个 O(k\sqrt k) 的做法。

感觉和直接计算 [x^k] 差不多？因为你考虑到了 (1-x)^n 好像跟 C_{k-i+n-1}^{n-1} 有点关系

由于你不是 \text{YK}，你根本不会被卡常，于是你随便就过去了

\text{Update 2021.9.6}

由于您是 \text{YK} ，您发愤图强写了四次fyt \text{fft} 的任意模数，于是你使用多项式 \text{AC} 了