題目鏈接

http://poj.org/problem?id=1430

題解

qaq寫了道水題……

在模\(2\)意義下重寫一下第二類Stirling數(shù)的遞推式: \[S(n,m)=S(n-1,m-1)+(S(n-1,m)\ \text{and}\ m)\]
令\(S'(n,m)=S(n+m,m)\), 那么遞推式變成了\(S'(n,m)=S'(n,m-1)+(S'(n-1,m)\ \text{and}\ m)\)
也就相當(dāng)于從\((0,0)\)走到\((n,m)\)的NE Lattice Path數(shù)目，且當(dāng)縱坐標為偶數(shù)時只能往上走不能往右走
那這個只能往上走不能往右走就相當(dāng)于把這一行刪掉了（因為對方案沒有任何影響），于是保留下來的行只有\([\frac{m-1}{2}]\)個
那么就是從\((0,0)\)走到\((n,[\frac{m-1}{2}])\)的NE Lattice Path條數(shù)，直接Lucas定理組合數(shù)計算即可
\(m=0\)要特判
時間復(fù)雜度\(O(T(\log n+\log m))\).

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #define llong long long using namespace std;inline int read() {int x=0; bool f=1; char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=0;for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');if(f) return x;return -x; }int comb0(int x,int y) {return x<y?0:1;} int comb(int x,int y) {if(x<2&&y<2) {return comb0(x,y);}return comb((x>>1),(y>>1))*comb0((x&1),(y&1)); }int main() {int T; scanf("%d",&T);while(T--){int n,m; scanf("%d%d",&n,&m);if(m==0) {printf("0\n"); continue;}n -= m; m = (m-1)>>1;printf("%d\n",comb(n+m,m));}return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ 1430 Binary Stirling Numbers (第二类斯特林数、组合计数)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。