BSUIR Open 2017 Finals补题
A
给定一棵 n n n个节点的树（ n ≤ 1000 n\le 1000 n≤1000），需要把所有边定向，使得恰好有m个点没有出边，求方案数。
Solution
记 d p [ u ] [ x ] [ 0 / 1 ] dp[u][x][0/1] dp[u][x][0/1]为以 u u u为节点的子树，除 u u u外有 x x x个节点没有出边，且 u u u有/无往子节点的出边的方案数。
若 v v v为 u u u的子节点，则状态转移方式如下:
- 连边为 v → u v\rightarrow u v→u
d p [ u ] [ x + Δ x ] [ 0 ] + = d p [ u ] [ x ] [ 0 ] ∗ ( d p [ v ] [ Δ x ] [ 0 ] + d p [ v ] [ Δ x ] [ 1 ] ) dp[u][x+\Delta x][0]+=dp[u][x][0]*(dp[v][\Delta x][0]+dp[v][\Delta x][1]) dp[u][x+Δx][0]+=dp[u][x][0]∗(dp[v][Δx][0]+dp[v][Δx][1])
d p [ u ] [ x + Δ x ] [ 1 ] + = d p [ u ] [ x ] [ 1 ] ∗ ( d p [ v ] [ Δ x ] [ 0 ] + d p [ v ] [ Δ x ] [ 1 ] ) dp[u][x+\Delta x][1]+=dp[u][x][1]*(dp[v][\Delta x][0]+dp[v][\Delta x][1]) dp[u][x+Δx][1]+=dp[u][x][1]∗(dp[v][Δx][0]+dp[v][Δx][1]) - 连边为 u → v u\rightarrow v u→v
d p [ u ] [ x + Δ x ] [ 0 ] + = ( d p [ u ] [ x ] [ 0 ] + d p [ u ] [ x ] [ 1 ] ) ∗ ( d p [ v ] [ Δ x ] [ 0 ] + d p [ v ] [ Δ x − 1 ] [ 1 ] ) dp[u][x+\Delta x][0]+=(dp[u][x][0]+dp[u][x][1])*(dp[v][\Delta x][0]+dp[v][\Delta x-1][1]) dp[u][x+Δx][0]+=(dp[u][x][0]+dp[u][x][1])∗(dp[v][Δx][0]+dp[v][Δx−1][1])
E
询问 1 1 1~ n n n的全排列中，有多少个满足 ∣ p i − i ∣ ≤ k , ∀ i ∈ [ 1 , n ] |p_i-i|\le k, \forall i\in [1,n] ∣pi−i∣≤k,∀i∈[1,n]( 0 ≤ k ≤ 9 , n ≤ 1 0 10 − k 0\le k\le 9, n\le 10^{10-k} 0≤k≤9,n≤1010−k)
Solution
记 d p [ i ] [ m a s k ] dp[i][mask] dp[i][mask]为填了第 1 1 1~ i i i个位置后，第 ( i − k ) (i-k) (i−k)~ ( i + k ) (i+k) (i+k)个位置填充状态为 m a s k mask mask的方案数。
状态转移方式如下：
d p [ i ] [ m a s k > > 1 ] = d p [ i − 1 ] [ m a s k ] dp[i][mask>>1]=dp[i-1][mask] dp[i][mask>>1]=dp[i−1][mask]( m a s k mask mask最低位是0)
d p [ i ] [ m a s k > > 1 ∣ 1 < < j ] = d p [ i − 1 ] [ m a s k > > 1 ] dp[i][mask>>1|1<<j]=dp[i-1][mask>>1] dp[i][mask>>1∣1<<j]=dp[i−1][mask>>1]( m a s k mask mask最低位是1且第 j + 1 j+1 j+1位是0）
（位置编号小于1的统一设为1，大于n的统一设为0）
普通dp: O ( n k C 2 k + 1 k ) O(nkC_{2k+1}^k) O(nkC2k+1k)
矩阵快速幂: O ( ( C 2 k + 1 k ) 3 log n ) O((C_{2k+1}^k)^3\log n) O((C2k+1k)3logn)
