省选模拟56

A. 取石子游戏

  对于这种取石子的题一个经典结论就是先手必败当且仅当所有堆的石子数异或和为0。

  所以就有了一个暴力的dp思路,$f[i][j][k]$表示当前枚举到第i堆石子,选取的石子堆数模d为j,异或和为k的方案数,转移显然。

  然后发现题中给了一个奇怪的条件,保证所有堆石子数总和不大,所以就不难想到给石子数排序,然后每次只转移能够得到的异或值,然后复杂度就合法了。

B. 路径计数

  容斥套路题(?)。

  考虑求出来两个数组,$f[i][j][k]$表示从$i$出发到$j$走了$k$步的方案数,$g[i][j][k]$表示从$i$出发到$j$走了$k$步且中途不经过$i$的方案数。

  然后考虑容斥,首先可以容斥出$a[i][j][k]$表示从$i$到$j$并且中途不经过$j$的方案数。

  然后继续容斥可以得到$b[i][j][k]$表示从i到i中途不经过j的方案数。

  然后继续容斥就可以得到答案了。

C. 方格操作

  首先可以发现,每一行的操作次数只和这一行上白色点个数的奇偶性有关。

  然后发现,可以交换行列,不会影响最终的答案。

  所以每个格子根据所在行列只有4种情况,然后将这些行列移动一下就可以得到一个等价的$2*2$矩阵,所以直接对于这个矩阵模拟就行了。

原文地址:https://www.cnblogs.com/hzoi-cbx/p/12589668.html