BSUIR Open 2017 Finals补题

A

给定一棵$n$个节点的树（$n\le 1000$），需要把所有边定向，使得恰好有m个点没有出边，求方案数。

Solution

记$dp[u][x][0/1]$为以$u$为节点的子树，除$u$外有$x$个节点没有出边，且$u$有/无往子节点的出边的方案数。
若$v$为$u$的子节点，则状态转移方式如下:

1. 连边为$v\to u$
   $$dp[u][x+\Delta x][0]+=dp[u][x][0]\ast (dp[v][\Delta x][0]+dp[v][\Delta x][1])$$
   $$dp[u][x+\Delta x][1]+=dp[u][x][1]\ast (dp[v][\Delta x][0]+dp[v][\Delta x][1])$$
2. 连边为$u\to v$
   $$dp[u][x+\Delta x][0]+=(dp[u][x][0]+dp[u][x][1])\ast (dp[v][\Delta x][0]+dp[v][\Delta x-1][1])$$

E

询问$1$~$n$的全排列中，有多少个满足$|p_i-i|\le k,\forall i\in [1,n]$($0\le k\le 9,n\le 10^{10-k}$)

Solution

记$dp[i][mask]$为填了第$1$~ $i$个位置后，第$(i-k)$~$(i+k)$个位置填充状态为 $mask$的方案数。
状态转移方式如下：
$dp[i][mask>>1]=dp[i-1][mask]$($mask$最低位是0)
$dp[i][mask>>1|1<<j]=dp[i-1][mask>>1]$($mask$最低位是1且第$j+1$位是0）
（位置编号小于1的统一设为1，大于n的统一设为0）
普通dp:$O(nk{C}_{2k+1}^k)$
矩阵快速幂:$O((C_{2k+1}^k{)}^3\log n)$