两个题推导是一样的，具体实现不一样，所以写一起了，以FJOI 2016 建筑师 的题面为标准
前后在组合意义下一样，现在只考虑前面，可以发现看到的这a个建筑将这一段划分成了a-1个区间，区间里的数随意填。
看起来可以用组合数算，但是还要考虑看到的建筑，所以我们把每个建筑和它后面这段区间合起来看。设区间的长度是len，这就是一个len+1个数的圆排列(等于len!，相当于固定一个开头后面随便排)
这样考虑前后就是将n-1个数划分为a+b-2个全排列，n-1是因为最高的那个在两边都没被算进去，是第一类斯特林数。同时a+b-2个圆排列之间还要选出来a-1个放前面，乘上组合数即可。现在关键是如何求第一类斯特林数。
FJOI那道题n*k不是很大，可以直接$O(nk)$递推，边界条件是$S[0][0]=1$，转移是$S[i][j]=S[i-1][j-1]+S[i-1][j]*(i-1)$
CF那道题只有一次询问，但是n,k都很大，我们考虑第一类斯特林数在第一维固定下的生成函数：$G(x)=prodlimits_{i=0}^{n-1}(x+i)$，x是从$s[i-1][j-1]$来的，i-1是从$s[i-1][j]*(i-1)$来的。用分治NTT优化
Code1
1 //Simple NTT 2 #include<cmath> 3 #include<cstdio> 4 #include<cctype> 5 #include<cstring> 6 #include<algorithm> 7 #define vint vector<int> 8 using namespace std; 9 const int N=2000006,mod=998244353; 10 int fac[N],inv[N],rev[N]; 11 int aa[N],bb[N],pw[30][2]; 12 int a,b,n,l1,l2,G,Gi,Ni; vint stl; 13 int Qpow(int x,int k) 14 { 15 if(k==1) return x; 16 int tmp=Qpow(x,k/2); 17 return k%2?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod; 18 } 19 int C(int a,int b) 20 { 21 return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod; 22 } 23 void SPJ() 24 { 25 if(!a||!b||n-1<a+b-2) printf("0"),exit(0); 26 if(n==1) printf("1"),exit(0); 27 } 28 void Pre() 29 { 30 fac[0]=inv[0]=1,G=3,Gi=Qpow(G,mod-2); 31 for(int i=1;i<=24;i++) 32 { 33 pw[i][0]=Qpow(G,(mod-1)/(1<<i)); 34 pw[i][1]=Qpow(Gi,(mod-1)/(1<<i)); 35 } 36 for(int i=1;i<=a+b;i++) fac[i]=1ll*fac[i-1]*i%mod; 37 inv[a+b]=Qpow(fac[a+b],mod-2); 38 for(int i=a+b-1;i;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod; 39 } 40 void Prework(vint &a,vint &b) 41 { 42 register int i; 43 l1=a.size()-1,l2=b.size()-1; 44 l1+=l2,l2=1; while(l2<=l1) l2<<=1; 45 a.resize(l2),b.resize(l2); 46 for(i=0;i<=l2;i++) aa[i]=a[i]; 47 for(i=0;i<=l2;i++) bb[i]=b[i]; 48 for(i=1;i<l2;i++) 49 rev[i]=(rev[i>>1]>>1)+(i&1)*(l2>>1); 50 } 51 void Trans(int *arr,int len,int typ) 52 { 53 register int i,j,k; 54 for(i=0;i<len;i++) 55 if(rev[i]>i) swap(arr[rev[i]],arr[i]); 56 for(i=2;i<=len;i<<=1) 57 { 58 int lth=i>>1,ort=pw[(int)log2(i)][typ==-1]; 59 for(j=0;j<len;j+=i) 60 { 61 int ori=1,tmp; 62 for(k=j;k<j+lth;k++,ori=1ll*ori*ort%mod) 63 { 64 tmp=1ll*ori*arr[k+lth]%mod; 65 arr[k+lth]=(arr[k]-tmp+mod)%mod; 66 arr[k]=(arr[k]+tmp)%mod; 67 } 68 } 69 } 70 if(typ==-1) 71 { 72 int Ni=Qpow(len,mod-2); 73 for(i=0;i<=len;i++) 74 arr[i]=1ll*arr[i]*Ni%mod; 75 } 76 } 77 vint NTT(vint a,vint b) 78 { 79 Prework(a,b); 80 Trans(aa,l2,1),Trans(bb,l2,1); 81 for(int i=0;i<l2;i++) aa[i]=1ll*aa[i]*bb[i]%mod; 82 Trans(aa,l2,-1); 83 vint ret; ret.clear(); 84 for(int i=0;i<l2;i++) ret.push_back(aa[i]); 85 return ret; 86 } 87 vint CDQ(int l,int r) 88 { 89 if(l==r) return {l,1}; 90 else 91 { 92 int mid=(l+r)/2; 93 vint a1=CDQ(l,mid),a2=CDQ(mid+1,r); 94 return NTT(a1,a2); 95 } 96 } 97 int main() 98 { 99 scanf("%d%d%d",&n,&a,&b); 100 SPJ(),Pre(),stl=CDQ(0,n-2); 101 printf("%d",1ll*C(a+b-2,a-1)*stl[a+b-2]%mod); 102 return 0; 103 }
Code2
1 #include<cmath> 2 #include<cstdio> 3 #include<cctype> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 const int N=50006,M=405,mod=1e9+7; 8 int fac[N],inv[N],S[N][M]; 9 int a,b,n,T,l1,l2,G,Gi,Ni; 10 int Qpow(int x,int k) 11 { 12 if(k==1) return x; 13 int tmp=Qpow(x,k/2); 14 return k%2?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod; 15 } 16 int C(int a,int b) 17 { 18 return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod; 19 } 20 bool SPJ() 21 { 22 if(!a||!b||n-1<a+b-2) 23 {puts("0"); return false;} 24 if(n==1) 25 {puts("1"); return false;} 26 return true; 27 } 28 void Pre() 29 { 30 register int i,j; 31 fac[0]=inv[0]=1,S[0][0]=1; 32 for(i=1;i<=1000;i++) fac[i]=1ll*fac[i-1]*i%mod; 33 inv[1000]=Qpow(fac[1000],mod-2); 34 for(i=999;i;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod; 35 for(i=1;i<=50000;i++) 36 for(j=1;j<=400;j++) 37 S[i][j]=(S[i-1][j-1]+1ll*(i-1)*S[i-1][j]%mod)%mod; 38 } 39 int main() 40 { 41 Pre(); 42 scanf("%d",&T); 43 while(T--) 44 { 45 scanf("%d%d%d",&n,&a,&b); 46 if(SPJ()) printf("%lld ",1ll*C(a+b-2,a-1)*S[n-1][a+b-2]%mod); 47 } 48 return 0; 49 }