1. [ABC411G] Count Cycles

   【题意简化】给定一个 $n(\le 20)$ 个节点 $m( m \le 2e5)$ 条边的无自环的无向图，求图中有多少个环，答案取 998244353 的余数。

   【分析】 $n$ 较小，可以状压。

2. P3092 [USACO13NOV] No Change G

   【题意简化】给定 $k(k\le 16)$ 枚硬币，每个硬币都有一定面值。给定 $n(\le 10^5)$ 件商品，每个硬币可以购买连续一段商品，不设找零的情况下，如果能够购买 $n$ 物品，询问做多能留下多少钱？不能购买，输出 -1

   【分析】硬币对应的 $k$ 较小，可以状压。

   可以提前利用双指针预处理每枚硬币开始购买位置，算出购买区间的右端点，记为 $f[i][l]$ , 表示硬币 $i$ 从 $l$ 开始购买，能够购买的右端点位置，利用双指针 $O(kn)$ 得到。

   再定义 $dp[s]$ 使用硬币状态 $s$ 最多能够购买多少枚硬币，转移方程：

   $dp[s|(1<<i)]=max(dp[s|(1<<i)],f[i][dp[s]+1])$.

   总时间复杂度：$O(kn+2^kk)$

学习完毕

{{ select(1) }}

• YES
• NO