CF1027E Inverse Coloring

考场上没敲出来（其实想到就挺好写的

捏组数据手动模拟一下：

\(\begin{bmatrix}1&0&1&1&1&0&1\\1&0&1&1&1&0&1\\0&1&0&0&0&1&0\\1&0&1&1&1&0&1\\0&1&0&0&0&1&0\\0&1&0&0&0&1&0\\1&0&1&1&1&0&1\end{bmatrix}\)

容易可以得出几个性质：

\(1.\) 确定第一行和第一列即可确定整个矩阵。

\(2.\) 每一个子矩阵由第一行和第一列连续的或组成，最大子矩阵大小即为第一行第一列最长连续段长度的乘积。

考虑对第一行和第一列。注意到第一行和第一列本质相同，只要对第一行即可。设为第一行前个元素，最长连续段长度为的方案数。会发现不是很好转移，考虑容斥。 该设为前个元素，最长连续段长度的方案数。转移：\(f_{i,j}=\sum_{i=1}^{\min(i,j)}f_{i-k,j}\) 。 设 \(g_i\) 为第一行最长连续段长度为的方案数。则 \(g_i=f_{n,i}-f_{n,i-1}\)。

最后分别枚举第一行第一列的最长连续段长度 \(i\) 和 \(j\)，如果满足 \(i \times j < k\),则将 \(g_i \times g_j\) 计入答案,时间复杂度是 \(O(n^3)\)。

考虑前缀和优化转移，时间复杂度为 \(O(n^2)\)。

\(Code\)

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int kmax = 3005;
const int Mod = 998244353;

int n, k;
long long f[kmax][kmax], g[kmax][kmax];
long long s[kmax][kmax], res;

int main() {
  // freopen("matrix.in", "r", stdin);
  // freopen("matrix.out", "w", stdout);
  scanf("%d%d", &n, &k);
  k--;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
      if (i == j) {
        g[i][j] = 1;
      } else {
        g[i][j] = ((f[i - 1][j] - f[i - j][j] + Mod) % Mod + s[i - j][min(j, i - j)]) % Mod;
      }
      f[i][j] = (f[i - 1][j] + g[i][j]) % Mod;
      s[i][j] = (s[i][j - 1] + g[i][j]) % Mod;
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= min(n, k / i); j++) {
      res = (res + 2ll * g[n][i] % Mod * g[n][j] % Mod) % Mod;
    }
  }
  printf("%lld\n", res);
  return 0;
}