题目链接
题目解法
一个朴素的结论是：\(fun(p)\le \frac{n\times (n+1)}{2}\)
所以可以把 \(lim\) 的范围缩小到 \(\frac{n\times (n+1)}{2}\)
首先可以得到一个简单的 \(O(n^6)\) 做法：
令 \(f_{i,j}\) 表示长度为 \(i\) 的排列，\(fun(p)=j\) 的排列数量
不难得到转移为：\(f_{i,j}(j\ge i)=\sum\limits_{k=0}^{i-1}\sum\limits_{p=0}^{j-i}f_{k,p}f_{i-1-k,j-i-p}\binom{i-1}{k}\)
考虑优化（感觉下面的过程还是很妙的）
在多项式上考虑，令 \(F_i(j)=f_{i,j}x^j\)
所以 \(F_i=x^i\sum\limits_{k=0}^{i-1}F_kF_{i-1-k}\binom{i-1}{k}\)
暴力卷是 \(O(n^4\log n)\) 的，不仅时间不行，而且模数是 \(10^9+7\)，没法 \(fft\)
换个角度考虑
\(F_n\) 是 \(\frac{n\times (n+1)}{2}\) 次多项式，我们只要知道 \(\frac{n\times (n+1)}{2}+1\) 个点值，就可以确定多项式的系数
这样就可以暴力找 \(\frac{n\times (n+1)}{2}+1\) 个 \(x\)，暴力求点值了
还原系数可以拉格朗日插值，模板题题解里面有一篇是还原系数的
时间复杂度 \(O(n^4)\)，但因为常数较大，所以我需要开 C++20 和火车头才能通过
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=210,P=1e9+7;
int n,lim,f[N],C[N][N],y[N*N];
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
int qmi(int a,int b){
int res=1;
for(;b;b>>=1){ if(b&1) res=1ll*res*a%P;a=1ll*a*a%P;}
return res;
}
int B,coef[N*N],knap[N*N],ans[N*N],inv[N*N];
void lagrange(){
coef[0]=1;
F(i,1,B){
DF(j,i,1) coef[j]=(coef[j-1]+1ll*coef[j]*(P-i))%P;
coef[0]=1ll*coef[0]*(P-i)%P;
}
F(i,1,B){
int coe=1;
F(j,1,B) if(i!=j) coe=1ll*coe*(i-j+P)%P;
coe=qmi(coe,P-2);coe=1ll*coe*y[i]%P;
knap[0]=1ll*coef[0]*(P-inv[i])%P;
F(j,1,B) knap[j]=1ll*(coef[j]+P-knap[j-1])*(P-inv[i])%P;
F(j,0,B) inc(ans[j],1ll*knap[j]*coe%P);
}
}
int main(){
n=read(),lim=read();
if(lim>n*(n+1)/2){ puts("0");exit(0);}
C[0][0]=1;
F(i,1,n) F(j,0,i) C[i][j]=(!j||i==j)?1:(C[i-1][j-1]+C[i-1][j])%P;
B=n*(n+1)/2+1;
F(i,1,B) inv[i]=qmi(i,P-2);
F(i,1,B){
f[0]=1;
int pw=1;
F(j,1,n){
f[j]=0;
F(k,0,j-1) inc(f[j],1ll*f[k]*f[j-1-k]%P*C[j-1][k]%P);
pw=1ll*pw*i%P;
f[j]=1ll*f[j]*pw%P;
}
y[i]=f[n];
}
lagrange();
int ANS=0;
F(i,lim,B) inc(ANS,ans[i]);
printf("%d\n",ANS);
return 0;
}