K-inversion(DP/多项式) | qkoqhh

题目链接

https://www.hackerrank.com/contests/101hack43/challenges/k-inversion-permutations/problem

题意

给定 $n$ 和 $m$ ，求有多少个 $n$ 的排列，满足该排列的逆序对个数为 $m$

$n\le10^5,m\le10^5$

题解

学习容斥的时候看到的，不过并没有用到容斥的方法。。

解法一

从最暴力的角度出发，设 $d[i][j]$ 为 $i$ 排列中逆序对为 $j$ 的个数

$d[i][j]=\sum_{k=0}^{i-1} d[i-1][j-k]$

这个 $DP$ 式子看起来就特别简单，事实上用多项式可以表示为

$\prod_{i=1}^n(1+x+\cdots+x^{i-1})=\prod_{i=1}^n\frac{1-x^i}{1-x}$

关键求 $\prod_{i=1}^n(1-x^i)$

如果 $n\rightarrow\infty$ ，那么这个为五边形数，但是 $n$ 有限，我们只能退而求其次，利用 $n\sqrt n$ 的暴力求解

设 $g[i][j]$ 为包含 $i$ 项次数为 $j$ 的系数，由于要保证数不大于 $n$ ，所以要把大小为 $n+1$ 的方案去掉

$g[i][j]=g[i][j-i]+g[i-1][j-i-1]-g[i-1][j-n-1]$

解法二

和 zlc 大佬讨论，他给出了一种复杂度更加优秀的方法

$\begin{aligned} \prod_{i=1}^n(1-x^i)=&e^{\textstyle\sum_{i=1}^n ln(1-x^i)}\\ =&e^{\textstyle\sum_{i=1}^n\sum_{j=1}^\infty-\frac{x^{in}}{n}} \end{aligned}$

然后这个直接类似埃筛就把指数的多项式搞定了，然后做多项式指数就可以了。。

但是模数不是 $NTT$ ，要用 $MTT$ 。。

然后跑得超慢。。比上面的 $O(m\sqrt m)$ 还慢。。

但仍不失为一个好思路orz zlc!!

解法三

和解法一的方法神似。。

仍然考虑式子

$d[i][j]=\sum_{k=0}^{i-1} d[i-1][j-k]$

发现可以转化为 $x_1+x_2+\cdots+x_n=m$ 的方案数

其中 $x_i$ 满足 $x_i\le i-1$ ，那么有

$\begin{aligned} \sum_{x_1,x_2,\cdots,x_n}[x_i\le i-1][\sum x=m]=&\prod_{i=1}^n[x_i\le i-1][\sum x=m] \\=&\prod_{i=1}^n([x\ge0]-[x\ge i])[\sum x=m] \\=&\sum_{S}[\sum x=m-\sum_{i\in S}x_i] \end{aligned}$

但是 $S$ 过大，我们需要对 $\sum_T x_i$ 归类，然后可以设和解法一一样的 $DP$ 方程，然后在 $O(m\sqrt m)$ 内求解

代码

解法一

/**
 *　　　　　　  　　┏┓　　 　┏┓
 * 　　　　　  　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　  　　┃　　　　　　　┃ 　
 * 　　　　　  　　┃　　　━　　 　┃
 * 　　　　　  　　┃　＞　　　＜　┃
 * 　　　　　  　　┃　　　　　　　┃
 * 　　　　　  　　┃...　⌒　... 　┃
 * 　　　　　　  　┃              ┃
 * 　　　　　　  　┗━┓          ┏━┛
 * 　　　　　　　　　┃          ┃　Code is far away from bug with the animal protecting　　　　　　　　　　
 * 　　　　　　　　　┃          ┃   神兽保佑,代码无bug
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┃  　　　　　　
 * 　　　　　　　　　┃          ┃
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┗━━━┓
 * 　　　　　　　　　┃              ┣┓
 * 　　　　　　　　　┃              ┏┛
 * 　　　　　　　　　┗┓┓┏━━━━━━━━┳┓┏┛
 * 　　　　　　　　　　┃┫┫       ┃┫┫
 * 　　　　　　　　　　┗┻┛       ┗┻┛
 */ 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<set>
#include<bitset>
#include<complex>
#include<cstdlib>
#include<assert.h>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1<<x)
#define lowbit(x) (x&(-x))
#define mid (x+y>>1)
#define sqr(x) ((x)*(x))
#define NM 200005
#define nm 400005
using namespace std;
const double pi=acos(-1);
const ll inf=1e9+7;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}


inline void reduce(ll&x){x+=x>>63&inf;}
int n,m,_t;
ll ans[NM],d[2][NM],s,p[NM],invp[NM],inv[NM];



int main(){
    n=read();m=read();
    p[0]=p[1]=inv[1]=invp[0]=invp[1]=1;
    inc(i,2,n+m)p[i]=p[i-1]*i%inf,inv[i]=inv[inf%i]*(inf-inf/i)%inf,invp[i]=invp[i-1]*inv[i]%inf;
    d[_t=0][0]=ans[0]=1;
    for(int i=1;i*(i+1)/2<=m;i++){
	_t^=1;mem(d[_t]);
	inc(j,i,m){
	    reduce(d[_t][j]=d[_t][j-i]-d[_t^1][j-i]);
	    if(j>=n+1)reduce(d[_t][j]+=d[_t^1][j-n-1]-inf);
	    reduce(ans[j]+=d[_t][j]-inf);
	}
	//inc(j,0,m)printf("%lld ",d[_t][j]);putchar('\n');
    }
    //inc(i,0,m)printf("%lld ",ans[i]);putchar('\n');
    inc(i,0,m)reduce(s+=p[n+i-1]*invp[i]%inf*invp[n-1]%inf*ans[m-i]%inf-inf);
    printf("%lld\n",s);
    return 0;
}

解法二：(这里模数没改)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<set>
#include<bitset>
#include<complex>
#include<assert.h>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1ll<<x)
#define mid (x+y>>1)
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define NM 300005
#define nm 65536
using namespace std;
const double pi=acos(-1);
const ll inf=998244353;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}



inline void reduce(ll&x){x+=x>>63&inf;}
inline ll qpow(ll x,ll t){
    ll s=1;
    for(;t;t>>=1,x=x*x%inf)if(t&1)s=s*x%inf;
    return s;
}
ll p[NM],inv[NM],invp[NM];

namespace Poly{
    int lim,bit,rev[NM],w[NM],W[NM];
    ll invn;
    void clear(ll*a,ll*b){if(a<b)memset(a,0,sizeof(ll)*(b-a));}
    void init(int m){
    for(lim=1,bit=0;lim<m;lim<<=1)bit++;invn=qpow(lim,inf-2);
    inc(i,1,lim-1)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
    ll t=qpow(3,(inf-1)/lim);W[0]=1;
    inc(i,1,lim)W[i]=W[i-1]*t%inf;
    }
    void fft(ll*a,int f=0){
    int n=lim;
    inc(i,1,n-1)if(i<rev[i])swap(a[i],a[rev[i]]);
    for(int k=1;k<n;k<<=1){
        int t=n/k>>1;
        for(int i=0,j=0;i<k;i++,j+=t)w[i]=W[f?n-j:j];
        for(int i=0;i<n;i+=k<<1)
        for(int j=0;j<k;j++){
            ll x=a[i+j],y=w[j]*a[i+j+k]%inf;
            reduce(a[i+j]=x+y-inf);reduce(a[i+j+k]=x-y);
        }
    }
    if(f)inc(i,0,n-1)a[i]=a[i]*invn%inf;
    }
    ll _a[NM],_b[NM];
    void inv(ll*b,ll*a,int m){
    if(m==1){b[0]=qpow(a[0],inf-2);return;}
    inv(b,a,m+1>>1);init(m<<1);
    copy(a,a+m,_a);clear(_a+m,_a+lim);clear(b+m,b+lim);
    fft(b);fft(_a);
    inc(i,0,lim-1)b[i]=b[i]*(2-_a[i]*b[i]%inf+inf)%inf;
    fft(b,1);clear(b+m,b+lim);
    }
    void ln(ll*b,ll*a,int m){
    inv(b,a,m);
    inc(i,0,m-2)_a[i]=a[i+1]*(i+1)%inf;
    init(m<<1);
    clear(_a+m-1,_a+lim);
    fft(_a);fft(b);
    inc(i,0,lim-1)b[i]=b[i]*_a[i]%inf;
    fft(b,1);
    dec(i,m-1,1)b[i]=b[i-1]*::inv[i]%inf;b[0]=0;
    }
    void exp(ll*b,ll*a,int m){
    if(m==1){b[0]=1;return;}
    exp(b,a,m+1>>1);
    ln(_b,b,m);
    inc(i,0,m-1)reduce(_b[i]=a[i]-_b[i]);_b[0]++;
    clear(_b+m,_b+lim);clear(b+m,b+lim);
    fft(_b);fft(b);
    inc(i,0,lim-1)b[i]=b[i]*_b[i]%inf;
    fft(b,1);
    }
}

ll ans,a[NM],b[NM];
int n,m;

int main(){
    n=read();m=read();
    p[0]=p[1]=invp[0]=invp[1]=inv[1]=1;
    inc(i,2,262144)p[i]=p[i-1]*i%inf,inv[i]=inv[inf%i]*(inf-inf/i)%inf,invp[i]=invp[i-1]*inv[i]%inf;
    inc(i,1,n)
    for(int j=i,k=1;j<=m;k++,j+=i)reduce(a[j]-=inv[k]);
    Poly::exp(b,a,m+1);
    inc(i,0,m)
    reduce(ans+=p[n+i-1]*invp[i]%inf*invp[n-1]%inf*b[m-i]%inf-inf);
    return 0*printf("%lld\n",ans);
}