problem

luogu-P2606

solution

我們對 $i??\frac{i}{2}?$ 遠沒有 $i?2?i,2?i+1$ 敏感，這其實就是個二叉樹，而且是個小根堆。

每個點的值都小于左右兒子的值（如果有左右兒子）。

設 $f(i):$ 樹大小為 $i$ 的合法方案數。

樹根肯定是定了的，然后從剩下的 $i?1$ 個數中選左子樹大小個數，剩下自然都歸為右子樹。

$f(i)=f(si{z}_{lson})?\left(\genfrac{}{}{0ex}{}{i?1}{si{z}_{lson}}\right)$。

組合數只是起分配編號的作用，分配后離散化成 $1,2,...,j$。

比如：對于 $f(5)$ 而言，根是 $1$，$p(1)=1$ 是固定的。

但是分給左子樹的編號可能是 $(2,3,4),(2,3,5),(2,4,5),(3,4,5)$ 有四種情況。

但是離散化后都是 $(1,2,3)$。

而 $f(3)$ 計算的就是當其被分配的編號為 $(1,2,3)$ 的時候的方案數。

這里面是嵌套下去的遞歸過程，分配編號方案數，拿到離散化的編號，繼續往字數分配編號…直到樹大小為 $1/2/3$，再開始層層回溯計算總方案數。

整個問題編號為 $1～n$，離散化后也是 $1～n$，所以 $f(n)$ 沒有分配編號的多種方案數。

所以 $f(i)$ 只是計算分配給其的離散化的連續編號然后是小根堆的答案。

這里的坑點是 $n$ 可能 $>m$。所以預處理階乘和逆元要注意上限的限制到底是多少。

code

#include <bits/stdc++.h> using namespace std; #define int long long #define maxn 1000005 int n, p; int fac[maxn], inv[maxn], siz[maxn], f[maxn], lg[maxn];int qkpow( int x, int y ) {int ans = 1;while( y ) {if( y & 1 ) ans = ans * x % p;x = x * x % p;y >>= 1;}return ans; }int calc( int n, int m ) {if( n < m ) return 0;else return fac[n] * inv[m] % p * inv[n - m] % p; }int C( int n, int m ) {if( ! m ) return 1;return C( n / p, m / p ) * calc( n % p, m % p ) % p; }#define lson i << 1 #define rson i << 1 | 1signed main() {scanf( "%lld %lld", &n, &p );fac[0] = inv[0] = 1, lg[0] = -1;for( int i = 1;i <= n;i ++ ) lg[i] = lg[i >> 1] + 1;int lim = min( n, p - 1 );for( int i = 1;i <= lim;i ++ ) fac[i] = fac[i - 1] * i % p;inv[lim] = qkpow( fac[lim], p - 2 );for( int i = lim - 1;i;i -- ) inv[i] = inv[i + 1] * ( i + 1 ) % p;f[1] = f[2] = 1, f[3] = 2;for( int i = 4, l = 1, r = 1;i <= n;i ++ ) {if( i - (1 << lg[i]) + 1 <= (1 << lg[i] - 1) ) l ++;else r ++;f[i] = C( i - 1, l ) * f[l] % p * f[r] % p;}printf( "%lld\n", f[n] % p );return 0; }

總結

以上是生活随笔為你收集整理的[ZJOI2010] 排列计数（dp + 组合数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。