[AGC013E] Placing Squares

link

难度

思维难度 : 四星

代码难度 : 一星

标签

$dp$ + 矩阵乘法 + 组合意义 + 计数

题解

考虑组合意义，就是一个有 $n$ 个格子，$n + 1$ 个间隔，每个间隔可以放隔板，把格子分成一些部分。每个格子都可以放 $1-2$ 个球，红球或蓝球，最后要求每个部分都有且仅有一个红球和一个蓝球。其中有一些间隔不能放隔板。求方案数。

对于一种放隔板的方案，放球的方案数显然是 $\prod_{i=1}^{k}a_i^2$ ，不同的放隔板的方案显然和放正方形的方案一一对应。

所有放隔板和放球的总方案数就是原题所有合法方案的贡献之和。

那么考虑新问题如何计数。如果不是关键点的话,可以推出转移 $A$​：

$f[i][j] 表示dp到第 i 个格子,当前部分有 j 个球\\ f[i][0] = f[i-1][0] + f[i-1][2] (放隔板或不放隔板)\\ f[i][1] = 2f[i-1][0] + f[i-1][1] + 2f[i-1][2] (放一个球，放另一个球，放隔板后放一个球)\\ f[i][2] = f[i-1][0] + f[i-1][1] + 2f[i-1][2] (放两个球，放另一个球，放隔板后放两个球或什么都不放)\\$

可以直接矩阵快速幂.

是关键点的话容易推出另一种转移 $B$.

如果当前 $dp$ 到的位置是关键点，乘上转移矩阵 $B$​​​ ，否则乘上转移矩阵 $A$ 。

因为关键点的个数 $\leq 10^5$ ， 所以关键点之间的部分可以矩阵快速幂优化.

Code:

#include <iostream>
#include <vector>
#define int long long

using namespace std;

const int M = 2e5 + 10, mod = 1e9 + 7;
struct Marix {
  int date[3][3];

  Marix() {}

  Marix (int v) {
    for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) date[i][j] = 0;
    for (int i = 0; i < 3; ++i) date[i][i] = v;
  }

  int * operator [] (int i) {
    return date[i];
  }
  
  Marix operator * (const Marix b) {
    Marix c(0);
    for (int i = 0; i < 3; ++i) {
      for (int j = 0; j < 3; ++j) {
        for (int k = 0; k < 3; ++k) {
          (c.date[i][j] += date[i][k] * b.date[k][j] % mod) %= mod;
        }
      }
    }
    return c;
  }
};

Marix qpow(Marix a, int b) {
  Marix res(1);
  while (b) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}

signed main() {
  ios::sync_with_stdio(false);
  cout.tie(NULL);
  cin.tie(NULL);
  Marix a, b, ans(1);
  a[0][0] = 1, a[0][1] = 2, a[0][2] = 1;
  a[1][0] = 0, a[1][1] = 1, a[1][2] = 1;
  a[2][0] = 1, a[2][1] = 2, a[2][2] = 2;
  b[0][0] = 1, b[0][1] = 2, b[0][2] = 1;
  b[1][0] = 0, b[1][1] = 1, b[1][2] = 1;
  b[2][0] = 0, b[2][1] = 0, b[2][2] = 1;
  int n, m;
  vector<int> mark;
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int x;
    cin >> x;
    mark.push_back(x);
  }
  int last = -1;
  for (auto it : mark) {
    int po = it - last - 1;
    last = it;
    ans = ans * qpow(a, po) * b;
  }
  ans = ans * qpow(a, n - last - 1);
  cout << ans[0][2] << endl;
  return 0;
}

总结

对于一些比较难计数的计数题, 可以考虑它的组合意义，一般都会转化为放球问题, 这时候就可以用比较简单的 $dp$ , 或熟悉的计数套路解决.