题意在一个 $N\times M$ 的田地里种草，有的地方不能种，要求不能有两块相邻的。求方案数。其中 $N,M\le 12$ 。题解状压dp。把图存下来，每次枚举时判断状态合不合法即可。$$\text{f}[i][j]+=\text{f}[i-1][k]$$#include<bits/stdc++.h>
#define ha 100000000
using namespace...
题意在 $N\times N$ 的棋盘里摆 $k$ 个国王，每个国王可以攻击周围 $8$ 个格子，求国王互不侵犯的摆法有多少种。其中 $N\le 9$ 。题解显然状压dp。可以预处理每一行的合法方案存在 $\text{s}[]$ ，合法方案即没有两个相邻的。用 $\text{f}[i][j][k]$ 表示在第 $i$ 行，合法方案编号为 $j$ ，放了 $k$ 个棋子的方案数。枚举上一行的状...
题意给出一棵树，定义 $\mathrm{dep}[i]$ 为 $i$ 的深度，$\mathrm{LCA}(i,j)$ 为 $i$ 与 $j$ 的最近公共祖先。有形如 $\text{(x y)}$ 的询问，求 $\sum\limits_{i \le x} \text{dep}(\text{LCA}(i,y))^k$ 。其中点数 $N\le 50000$ ，询问数 $M\le 50000$ 。...