s3mple
给定模数 \(P\) 和不超过 \(10\) 组 \(n,X\)，请问有多少个 \(n\) 的排列 \(p\)，满足 \(X=\sum_{i=1}^n v_i\)，其中 \(v_i=\min_{p_j>p_i}|i-j|\)。
\(n\le 200,X,P\le 10^9\)
容易想到笛卡尔树，对于一个节点，它的 \(v\) 就是 \(1+(左右子树大小的较小值)\)，其中这个 "1+" 可以变成把 X-=n，就可以扔掉了。
于是就有朴素的 \(O(n^2x^2)\) DP 做法（如果取 \(x=O(n^2)\) 就是 \(O(n^6)\)）。设 \(f(i,j)\) 表示子树大小为 \(i\)，\(\sum v'=j\)，填入 \(1\sim i\) 的方案数。\(f(i,j)=\sum_{k=0}^{i-1}\sum_{p=0}^{j}f(k,p)f(i-1-k,j-p-\min(k,i-1-k)){i-1\choose k}\)。可以获得 ≈60 分的部分分。（但是赛时我以为只能得 20 分就写了一个更好写的 20 分 next_permutation）
考虑转移方程，发现 \(p+(j-p-\min(k,i-1-k))=j-\min(k,i-1-k)(定值)\)，这很像卷积，所以把 \(f(i)\) 的各项看成多项式对应次数项的系数，枚举 \(k\)，就是 \(f(k)\) 和 \(f(i-1-k)\) 两个多项式的卷积。暴力卷积还是不行，其他卷积方式也不够快，我们可以考虑【套路】多项式卷积可以只维护每个多项式的点值，卷就是对应相乘，这样就可以 \(O(X)\) 地维护：\(f(i)=\sum_{k=0}^{i-1}f(i)*f(n-1-i)\cdot x^{\min(k,i-1-k)}\)（还要乘 \(x^{\min(k,i-1-k)}\) 的原因是，卷起来对应的是 \(j-\min(k,i-1-k)\)，但实际上应该对应 \(j\)）。考虑到 \(X\) 比较大，似乎没什么用，而部分分中有 \(X\) 比较小的提示，经过打表可以发现，\(X\) 的有效值是 \(750\) 左右。这样就可以 \(O(750n^2)\) 地求出每个 \(f(i)\) 的点值表示。
问题是，我们要输出的答案相当于是多项式系数，点值表示在模 \(P\) 意义下如何转为系数表示呢？这是拉格朗日插值的经典算法，考虑公式 \(f(x)=\sum_{i=1}^ny_i\prod_{j\ne i}{x-x_j\over x_i-x_j}\)，原先我们把 \(x\) 代入差值，如今我们从另一个角度考虑，把它化简成一个关于 \(x\) 的多项式，具体方法是，分母和 \(y_i\) 都是常数，上面的 \(\prod_{j\ne i} (x-x_j)\) 可以预处理出 \(\prod_{j=1}^n(x-x_j)\) 的系数表示，然后每次做 \(O(n)\) 的多项式除法，除以 \((x-x_i)\)，最后把所有 \(n\) 个得数加起来。 这样一来，便可以对于每一组询问在 \(O(800^2)\) 的复杂度内解决。
总复杂度 \(O(750n^3+10\times 750^2)\)。
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
using namespace std;
const int N=205,kM=780;
int n,axe,mod,f[N][kM],C[N][N],X[kM],T[kM],res[kM],inv[kM],jc[kM],ijc[kM],mi[kM][N];
inline void add(int &x,int y){(x+=y)>=mod&&(x-=mod);}
inline int qp(int a,int b){
int c=1;for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)c=1ll*c*a%mod;return c;
}
void solve(){
if(axe<n||axe>770){puts("0");return;}
axe-=n;
int ans=0;
for(int i=1;i<=770;i++){
int o=f[n][i];
for(int j=1;j<=770;j++)if(i!=j){
if(i>j)o=1ll*o*inv[i-j]%mod;
else o=1ll*o*(mod-1ll)%mod*inv[j-i]%mod;
}
for(int j=0;j<=770;j++)T[j]=X[j],res[j]=0;
for(int j=770;j;j--){
res[j-1]=T[j],add(T[j-1],1ll*i*T[j]%mod);
}
add(ans,1ll*o*res[axe]%mod);
}
cout<<ans<<'\n';
}
int main(){
cin>>mod;
jc[0]=ijc[0]=inv[0]=1;
for(int i=1;i<=770;i++)f[1][i]=1,f[0][i]=1,jc[i]=1ll*jc[i-1]*i%mod;
for(int i=1;i<=770;i++){
mi[i][0]=1;
for(int j=1;j<=200;j++)mi[i][j]=1ll*mi[i][j-1]*i%mod;
}
ijc[770]=qp(jc[770],mod-2);
for(int i=769;i;i--)ijc[i]=ijc[i+1]*(i+1ll)%mod;
for(int i=1;i<=770;i++)inv[i]=1ll*ijc[i]*jc[i-1]%mod;
C[0][0]=1;
for(int i=1;i<=200;i++){
C[i][0]=1;
for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
for(int en=2;en<=200;en++){
for(int i=0;i<en;i++){
for(int j=1;j<=770;j++)add(f[en][j],1ll*f[i][j]*f[en-1-i][j]%mod*C[en-1][i]%mod*mi[j][min(i,en-1-i)]%mod);
}
}
//Now convert f[n] from dianzhi representation to xishu representation
//First calculate (x-1)*(x-2)*(x-3)*...*(x-770), namely polynomial X
//Then, for each i<=770:
// first preprocess o=yi*\prod_{i!=j}(1/(i-j))
// then get X'=X/(x-i)
//\sum o*X' will be the final polinomial
for(int i=0;i<=770;i++)X[i]=0; X[0]=1;
for(int i=1;i<=770;i++){
for(int j=770;j;j--)X[j]=(X[j-1]+(mod-1ll)*i%mod*X[j]%mod)%mod;
X[0]=(mod-1ll)*i%mod*X[0]%mod;
}
while(cin>>n>>axe)solve();
}