第一類斯特林數
s 1 n m s1_n^m s1nm表示将 n n n個數放進 m m m個圓排列的方案數。
有一個顯然的遞推式:
s 1 n m = s 1 n − 1 m − 1 + ( n − 1 ) s 1 n − 1 m s1_n^m=s1_{n-1}^{m-1}+(n-1)s1_{n-1}^m s1nm=s1n−1m−1+(n−1)s1n−1m,對應的意義:要麼第 n n n個單獨構成一個新的圓排列,要麼放在之前某個數的後面。
還有一種組合意義:一共進行 n n n次操作,第 i i i次可以添加跟第 1 1 1~ i − 1 i-1 i−1中任意一種物品相同的舊物品或者添加一種新物品,問最後一共有 m m m中不同物品的方案數,由此可以推出第一類斯特林數的生成函數:
∏ i = 0 n − 1 ( x + i ) \prod_{i=0}^{n-1}(x+i) ∏i=0n−1(x+i)
到這裡就有兩種挺明顯的預處理斯特林數方法了:
- 如果要求出每一個 s 1 i j s1_i^j s1ij,可以用 O ( n m ) O(nm) O(nm)遞推
- 如果隻用求出每一個 s 1 a k , a s1_a^k,a s1ak,a為定值,可以上分治 f f t fft fft做到 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)
但有些毒瘤出題人偏偏會卡你的分治 f f t fft fft,需要我們在更短的時間内求出某一行的值。
于是就有了下面的倍增算法:
假設我們已經求出了 f n ( x ) = ∏ i = 0 n − 1 ( x + i ) = ∑ i = 0 n a i x i f_n(x)=\prod_{i=0}^{n-1}(x+i)=\sum_{i=0}^na_ix^i fn(x)=∏i=0n−1(x+i)=∑i=0naixi的系數數組 a a a
現在要求的是 f 2 n ( x ) = ∏ i = 0 2 n − 1 ( x + i ) f_{2n}(x)=\prod_{i=0}^{2n-1}(x+i) f2n(x)=∏i=02n−1(x+i)
那麼相當于隻用求一個 g n ( x ) = ∏ i = n 2 n − 1 ( x + i ) g_n(x)=\prod_{i=n}^{2n-1}(x+i) gn(x)=∏i=n2n−1(x+i),這樣 f 2 n ( x ) = f n ( x ) g n ( x ) f_{2n}(x)=f_n(x)g_n(x) f2n(x)=fn(x)gn(x)
然後進入退式子環節:
g n ( x ) = ∏ i = n 2 n − 1 ( x + i ) = ∏ i = 0 n − 1 ( x + n + i ) = ∑ i = 0 n a i ( x + n ) i g_n(x)=\prod_{i=n}^{2n-1}(x+i)=\prod_{i=0}^{n-1}(x+n+i)=\sum_{i=0}^na_i(x+n)^i gn(x)=∏i=n2n−1(x+i)=∏i=0n−1(x+n+i)=∑i=0nai(x+n)i
把後面的 ( x + n ) i (x+n)^i (x+n)i給二項式展開一波:
g n ( x ) = ∑ i = 0 n a i ∑ j = 0 i C i j x j n i − j g_n(x)=\sum_{i=0}^na_i\sum_{j=0}^iC_i^jx^jn^{i-j} gn(x)=∑i=0nai∑j=0iCijxjni−j
然後拆開 C i j C_i^j Cij并改變枚舉順序
⇒ g n ( x ) = ∑ j = 0 n x j j ! ∑ i = j n a i i ! ∗ n j − i ( j − i ) ! \Rightarrow g_n(x)=\sum_{j=0}^n\frac{x^j}{j!}\sum_{i=j}^na_ii!*\frac{n^{j-i}}{(j-i)!} ⇒gn(x)=∑j=0nj!xj∑i=jnaii!∗(j−i)!nj−i
然後将 n j − i ( j − i ) ! \frac{n^{j-i}}{(j-i)!} (j−i)!nj−i這個數組給 r e v e r s e reverse reverse一下就變成了卷積的形式,可以用 f f t fft fft處理後面一坨。
這樣就做完了。
代碼:
//mul函數是自己封裝的多項式乘法函數
int n,A,B,a[N],b[N],pos[N],pw[N],tmp[N],fac[N],ifac[N],lim,tim;
inline void solve(int len){
if(len==1){a[1]=1;return;}
if(len&1){
solve(len-1);
for(ri i=len;i;--i)a[i]=add(a[i-1],mul(a[i],len-1));
return;
}
solve(len>>1);
init(len);
int mid=len>>1;
pw[0]=1;
for(ri i=1;i<=mid;++i)pw[i]=mul(pw[i-1],mid);
for(ri i=0;i<=mid;++i)tmp[i]=mul(a[i],fac[i]),b[i]=mul(pw[i],ifac[i]);
for(ri i=mid+1;i<lim;++i)tmp[i]=b[i]=0;
reverse(b,b+mid+1);
mul(tmp,b);
for(ri i=0;i<=mid;++i)b[i]=mul(b[i+mid],ifac[i]);
for(ri i=mid+1;i<lim;++i)b[i]=0;
mul(b,a);
}
一道闆題:codeforces960G
推出來式子是 C a + b − 2 a − 1 s 1 n − 1 a + b − 2 C_{a+b-2}^{a-1}s1_{n-1}^{a+b-2} Ca+b−2a−1s1n−1a+b−2,這個組合意義很簡單,然後套上闆子即可。
代碼:
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
typedef long long ll;
const int mod=998244353;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)ret=mul(ret,a);return ret;}
const int N=4e5+5;
int n,A,B,a[N],b[N],pos[N],pw[N],tmp[N],fac[N],ifac[N],lim,tim;
inline void init(const int&up){
lim=1,tim=pos[0]=0;
while(lim<=up)lim<<=1,++tim;
for(ri i=0;i<lim;++i)pos[i]=(pos[i>>1]>>1)|((i&1)<<(tim-1));
}
inline void ntt(int *a,const int&type){
for(ri i=0;i<lim;++i)if(i<pos[i])swap(a[i],a[pos[i]]);
int wn,w,a0,a1,typ=type==1?3:(mod+1)/3,mult=(mod-1)>>1;
for(ri mid=1;mid<lim;mid<<=1,mult>>=1){
wn=ksm(typ,mult);
for(ri j=0,len=mid<<1;j<lim;j+=len){
w=1;
for(ri k=0;k<mid;++k,w=mul(w,wn)){
a0=a[j+k],a1=mul(a[j+k+mid],w);
a[j+k]=add(a0,a1),a[j+k+mid]=dec(a0,a1);
}
}
}
if(type==-1)for(ri i=0,inv=ksm(lim,mod-2);i<lim;++i)a[i]=mul(a[i],inv);
}
inline void mul(int *a,int *b){
ntt(a,1),ntt(b,1);
for(ri i=0;i<lim;++i)b[i]=mul(a[i],b[i]);
ntt(b,-1);
}
inline void solve(int len){
if(len==1){a[1]=1;return;}
if(len&1){
solve(len-1);
for(ri i=len;i;--i)a[i]=add(a[i-1],mul(a[i],len-1));
return;
}
solve(len>>1);
init(len);
int mid=len>>1;
pw[0]=1;
for(ri i=1;i<=mid;++i)pw[i]=mul(pw[i-1],mid);
for(ri i=0;i<=mid;++i)tmp[i]=mul(a[i],fac[i]),b[i]=mul(pw[i],ifac[i]);
for(ri i=mid+1;i<lim;++i)tmp[i]=b[i]=0;
reverse(b,b+mid+1);
mul(tmp,b);
for(ri i=0;i<=mid;++i)b[i]=mul(b[i+mid],ifac[i]);
for(ri i=mid+1;i<lim;++i)b[i]=0;
mul(b,a);
}
inline int C(int n,int m){return n<m?0:mul(mul(fac[n],ifac[m]),ifac[n-m]);}
int main(){
n=read(),A=read(),B=read();
if(n==1)return cout<<(A==1&&B==1),0;
fac[0]=fac[1]=ifac[0]=ifac[1]=1;
for(ri i=2;i<=n;++i)fac[i]=mul(fac[i-1],i),ifac[i]=mul(ifac[mod-mod/i*i],mod-mod/i);
for(ri i=2;i<=n;++i)ifac[i]=mul(ifac[i-1],ifac[i]);
solve(n-1);
cout<<mul(a[A+B-2],C(A+B-2,A-1));
return 0;
}