题面
题解
这居然是一道语文题？
首先不难看出，因为每一次相邻元素交换最多减少一个逆序对，所以至少(m)次交换就代表这个序列的逆序对个数为(m)
我们考虑一下，假设现在已经放完了(i-1)个数，当放入第(i)个数的时候会对逆序对个数造成什么影响
如果第(i)个数放在最后，新增逆序对个数为(0)，如果插在最后一个数前面，新增逆序对为(1)……
综上，第(i)个数插入之后新加的逆序对数为(0,1,...,i-1)
那么不难看出，新增逆序对数的这个数列，和原序列是有一一对应关系的
那么我们就可以把它写成生成函数的形式了，题目转为求
的第(m)次项的系数
然后就要开始推倒了
所以直接上多项式即可
我们来考虑两个柿子的组合意义
({1over 1-x}=sum_{i=0}^infty x^i)，那么(left(1over 1-x ight)^n)的第(k)项系数就代表(a_1+a_2+...+a_n=k)的非负整数解的个数，根据隔板法可得它的第(k)项系数为({k+n-1choose n-1})
然后考虑后面那个，可以看做有(n)个物品，第(i)个物品体积为(i)，求用这些物品填满体积为(k)的背包的方案数，有符号
这就相当于是一个背包，因为背包内部是无序的，所以它等价于求和为(k)的严格上升子序列的个数
我们设(f_{i,j})表示长度为(i)，和为(j)的严格上升子序列的个数，然后考虑这玩意儿怎么转移
可以新增一个物品，那么方案数为(f_{i-1,j-i})（先把所有物品(+1)，再新放入一个(1)进去）
也可以不放物品，把所有数(+1)，方案数为(f_{i,j-i})
不过这样转移可能会有不合法的，因为放的数最大值不能超过(n)，所以要减去(f_{i-1,j-(n+1)})
记得前面要带上符号
即为
因为每种体积的物品最多一个，所以放的物品最多不超过(O(sqrt{m}))
那么多项式(prod_{k=1}^n(1-x^k))第(i)项的系数就是(sum_j f_{j,i})
然后把这两个多项式卷个积就能得到答案了
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
const int N=2e5+5,P=998244353;
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
R int res=1;
for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);
return res;
}
int fac[N],ifac[N],f[N],g[N],dp[555][N];
int n,m,res;
inline int C(R int n,R int m){return m>n?0:1ll*fac[n]*ifac[m]%P*ifac[n-m]%P;}
int main(){
// freopen("testdata.in","r",stdin);
scanf("%d%d",&n,&m);
fac[0]=ifac[0]=1;fp(i,1,n+m)fac[i]=mul(fac[i-1],i);
ifac[n+m]=ksm(fac[n+m],P-2);fd(i,n+m-1,1)ifac[i]=mul(ifac[i+1],i+1);
fp(i,0,m)f[i]=C(i+n-1,n-1);
dp[0][0]=1,g[0]=1;
int d=1;
fp(j,2,m)if((1ll*j*(j+1)>>1)>=m){d=j;break;}
fp(i,1,d){
fp(j,0,m){
j>=i?dp[i][j]=dec(dp[i][j-i],dp[i-1][j-i]):0;
j>=n+1?dp[i][j]=add(dp[i][j],dp[i-1][j-n-1]):0;
}
fp(j,0,m)g[j]=add(g[j],dp[i][j]);
}
fp(i,0,m)res=add(res,mul(f[i],g[m-i]));
printf("%d
",res);
return 0;
}