Codeforces 题解 CF106694J 草莓牛奶 题解
钦定第一个数为 $p$，令 $m=n-p$ 表示比 $p$ 大的数的个数，那么答案就是
\[\sum_{m=0}^{n-1}\binom{n-1}m\sum_{j_1-j_2\ge k}{m\brack j_1}{n-1-m\brack j_2}\]表示从 $n-1$ 个下标中选 $m$ 个放 $>p$ 的那些数字。第一类斯特林数 ${m\brack j_1}$ 表示排列 $[m]$ 恰有 $j_1$ 个前缀最值的方案数。
第一类斯特林数的生成函数 $n\brack i$ 是 $\sum\limits_{i}{n\brack i}x^i=x(x+1)(x+2)\cdots(x+n-1)=x^{\overline n}$。
而我们还有一个第一类斯特林数的范德蒙德卷积形式，或者叫做上升幂的二项式定理。
\[(x+y)^{\overline n}=\sum_{m=0}^n\binom nmx^{\overline m}y^{\overline{n-m}}\]回到之前那个式子，我们用 $x$ 作为 $j_1$ 那块指示元，$x^{-1}$ 作为 $j_2$ 那块指示元。这样 $j_1-j_2\ge k$ 就变成求指数 $\ge k$ 的那些项的系数和。
\[\sum_{i\ge k}[x^i](x+x^{-1})^{\overline{n-1}}=\sum_{j=k}^{n-1}[x^j]\prod_{i=0}^{n-2}(x+x^{-1}+i)\]不妨平移，乘上一个 $x^{n-1}$
\[\sum_{i\ge k}[x^i](x+x^{-1})^{\overline{n-1}}=\sum_{j=k+n-1}^{2n-2}[x^j]\prod_{i=0}^{n-2}(1+ix+x^2)\]注意到对称性，我们把 $\sum\limits_{i=k+n-1}^{2n-2}$ 沿着 $n-1$ 翻转答案不变。
\[\sum_{i\ge k}[x^i](x+x^{-1})^{\overline{n-1}}=\sum_{j=0}^{n-1-k}[x^j]\prod_{i=0}^{n-2}(1+ix+x^2)\]最后分治 NTT 处理即可。
#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int P=998244353;
struct mint{
int d;
mint()=default;
mint(int x):d(x){}
friend std::istream&operator>>(std::istream&x,mint&y){return x>>y.d;}
friend std::ostream&operator<<(std::ostream&x,mint y){return x<<y.d;}
friend mint operator+(mint x,mint y){return (x.d+=y.d)<P?x.d:x.d-P;}
mint&operator+=(mint z){return (d+=z.d)<P?d:d-=P,*this;}
friend mint operator-(mint x,mint y){return (x.d-=y.d)<0?x.d+P:x.d;}
mint&operator-=(mint z){return (d-=z.d)<0?d+=P:d,*this;}
friend mint operator*(mint x,mint y){return int(1ll*x.d*y.d%P);}
mint&operator*=(mint z){return d=int(1ll*d*z.d%P),*this;}
static mint qpow(int x,int y=P-2){int z=1;for(;y;y>>=1,x=int(1ll*x*x%P))if(y&1)z=int(1ll*x*z%P);return z;}
friend mint operator/(mint x,mint y){return x*=qpow(y.d);}
mint&operator/=(mint z){return (*this)*=qpow(z.d);}
friend mint operator^(mint x,mint y){return qpow(x.d,y.d);}
mint&operator^=(mint z){return *this=qpow(d,z.d);}
mint operator()(mint z)const{return qpow(d,z.d);}
mint&operator[](mint z){return *this=qpow(d,z.d);}
mint inv()const{return qpow(d);}
mint pow(mint z)const{return qpow(d,z.d);}
int operator+()const{return d;}
mint operator-()const{return d?P-d:0;}
int operator~()const{return ~d;}
};
mint operator""_m(lolu x){return mint(int(x%P));}
struct poly:vector<mint>{
using vector<mint>::vector;
static unt bswp(unt num,int len=32){
num=(num>>16)|(num<<16);
num=(num&0xff00ff00)>>8|(num&0x00ff00ff)<<8;
num=(num&0xf0f0f0f0)>>4|(num&0x0f0f0f0f)<<4;
num=(num&0xcccccccc)>>2|(num&0x33333333)<<2;
num=(num&0xaaaaaaaa)>>1|(num&0x55555555)<<1;
return num>>(32-len);
}
void dft(int T){
#define F (*this)
for(int i=0;i<siz(F);i++)
if(int j=bswp(i,__lg(siz(F)));i<j)std::swap(F[i],F[j]);
for(int k=1;k<siz(F);k<<=1){
mint w1=mint(3)^(mint(P-1)/(k*2)),u;
if(T!=1)w1=1/w1;
for(int i=0;i<siz(F);i+=k*2){
u=1;
for(int j=i;j<i+k;j++,u*=w1){
mint c1=F[j],c2=u*F[j+k];
F[j]=c1+c2;
F[j+k]=c1-c2;
}
}
}
#undef F
}
friend istream&operator>>(istream&x,poly&y){
int len;x>>len;y.resize(len+1);
return x;
}
friend poly operator*(poly F,poly G){
int tmp=siz(F)+siz(G)-1;
int len=1<<(__lg(tmp-1)+1);
F.resize(len);G.resize(len);
F.dft(1);G.dft(1);
for(int i=0;i<siz(F);i++)F[i]*=G[i];
F.dft(-1);
mint ziv=mint(siz(F)).inv();
for(int i=0;i<siz(F);i++)F[i]*=ziv;
F.resize(tmp);
return F;
}
poly&operator*=(const poly&f){return(*this)=(*this)*f;}
friend poly operator+(const poly&x,const poly&y){
poly z=x;
z.resize(max(siz(x),siz(y)));
for(int i=0;i<siz(y);i++)z[i]+=y[i];
return z;
}
friend poly operator-(const poly&x,const poly&y){
poly z=x;
z.resize(max(siz(x),siz(y)));
for(int i=0;i<siz(y);i++)z[i]-=y[i];
return z;
}
poly&operator+=(const poly&t){return (*this)=(*this)+t;}
friend poly operator*(poly x,mint y){
for(int i=0;i<siz(x);i++)x[i]*=y;
return x;
}
friend poly operator*(mint y,poly x){
for(int i=0;i<siz(x);i++)x[i]*=y;
return x;
}
};
constexpr int N=1e6+7;
int n,k;
poly F[N];
poly times(const poly&x,const poly&y){
poly z(siz(x)+siz(y)-1);
for(int i=0;i<siz(x);i++)for(int j=0;j<siz(y);j++)
z[i+j]+=x[i]*y[j];
return z;
}
poly solve(int l,int r){
// if(l==r)return F[l];
if(r-l<=50){
poly tmp=F[l];
for(int i=l+1;i<=r;i++)
tmp=times(tmp,F[i]);
return tmp;
}
int mid=(l+r)/2;
poly tmp=solve(l,mid)*solve(mid+1,r);
if(siz(tmp)>n-k)tmp.resize(n-k);
return tmp;
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;cin>>T;while(T--){
cin>>n>>k;
for(int i=0;i<=n-2;i++)
F[i].assign({1,i,1});
poly G=solve(0,n-2);
mint ans=0;
for(int i=0;i<n-k;i++)
ans+=G[i];
cout<<ans<<'\n';
}
// cerr<<clock();
return 0;
}