考虑到因为有横轴数轴两部分的限制,不妨先固定下来一部分的限制再处理另一部分。
对于这题来说横轴竖轴本质是相同的,于是不妨考虑固定横轴。
如果知道了横轴的分割,那么对于竖轴上就可以根据分割情况知道合法的分割了。
即考虑记 \(f_i\) 为考虑了竖轴的前 \(i\) 列,第 \(i\) 列为最后一个划分的最后一列的方案数。
考虑转移的 \(f_j\to f_i\),那么 \(j\) 就要满足对于横轴的每一个划分,\((j, i]\) 内都只有 \(2\) 个 \(\texttt{Y}\)。
能够发现,转移时 \(i\) 对应的 \(j\) 应当是一个区间范围内的,于是可以前缀和优化 DP,复杂度就是 \(\mathcal{O}(km)\),其中 \(k\) 是横轴划分的段数。
于是接下来的问题就来到了横轴,由上述的讨论可知现在的问题就是尽量小化横轴划分的 \(\sum k\)(因为复杂度为 \(m\sum k\))。
那么接下来的想法就是找一些合法的横轴划分的必要条件,缩小这个 \(\sum k\) 了。
考虑到因为竖轴的划分对于所有横轴是相同的,这说明对于每个横轴划分出的部分内部的块数是相同的,进一步说明了每个横轴划分出的部分的 \(\texttt{Y}\) 的个数是相同的。
所以说可以枚举 \(\sum\limits_{i = 1}^n \sum\limits_{j = 1}^m [s_{i, j} = \texttt{Y}]\) 的因数 \(d\),然后按照横轴划分的每部分内的 \(\texttt{Y}\) 的个数都为 \(d\) 去尝试划分。
如果能够成功划分,那么就可以 DP,并且用乘法原理乘上横轴划分的方案数。
对于横轴划分的方案数,其实就是因为两个划分的块中可能有全 \(\texttt{X}\) 的行,这一行给任意一边都是不影响划分的,统计比较简单不在此阐述,可以参考实现。
分析一下 \(\sum k\),本人暂时只会感性理解,考虑到其实还是当每一行的 \(\texttt{Y}\) 的个数都相同最劣,因为这个时候能够尽量满足足够多的划分(?)。
于是可以知道 \(\sum k\) 应当是 \(\mathcal{O}(n\ln n)\) 级别的。
时间复杂度 \(\mathcal{O}(d(S)n + nm\ln n)\),其中 \(S = \sum\limits_{i = 1}^n \sum\limits_{j = 1}^m [s_{i, j} = \texttt{Y}]\),\(d(x)\) 表示 \(x\) 的因数个数。
#include<bits/stdc++.h>
using ll = long long;
constexpr ll mod = 998244353;
const int maxn = 2e3 + 10;
char s[maxn][maxn];
int sum[maxn][maxn];
int val[maxn];
int L[maxn], R[maxn];
ll g[maxn];
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%s", s[i] + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (s[i][j] == 'Y');
if (! sum[n][m])
return puts("0"), 0;
int nst = 1, ned = n;
while (sum[nst][m] == 0) nst++;
while (sum[ned - 1][m] == sum[n][m]) ned--;
ll ans = 0;
for (int d = 2; d <= sum[n][m]; d += 2)
if (sum[n][m] % d == 0) {
ll f = 1;
std::vector<std::pair<int, int> > seg;
for (int i = nst, j = nst; i <= ned; i = j) {
while (j <= ned && sum[j][m] - sum[i - 1][m] < d) j++;
if (j > ned || sum[j][m] - sum[i - 1][m] > d) {f = 0; break;}
seg.emplace_back(i, j);
int c = 1; j++;
while (j <= ned && sum[j][m] == sum[j - 1][m]) j++, c++;
(f *= c) %= mod;
}
if (! f)
continue;
for (int i = 1; i <= m; i++)
L[i] = 0, R[i] = i - 1;
for (int id = 0; id < seg.size(); id++) {
auto [x, y] = seg[id];
for (int i = 0; i <= m; i++)
val[i] = sum[y][i] - sum[x - 1][i];
std::unordered_map<int, int> mx, mn;
for (int i = 0; i <= m; i++)
mx[val[i]] = i;
for (int i = m; ~ i; i--)
mn[val[i]] = i;
for (int i = 1; i <= m; i++)
if (mx.count(val[i] - 2)) {
R[i] = std::min(R[i], mx[val[i] - 2]);
L[i] = std::max(L[i], mn[val[i] - 2]);
} else
R[i] = -1;
}
g[0] = 1ll;
for (int i = 1; i <= m; i++) {
if (L[i] <= R[i])
g[i] = (g[R[i]] - (L[i] ? g[L[i] - 1] : 0ll) + mod) % mod;
else
g[i] = 0;
(g[i] += g[i - 1]) %= mod;
}
(ans += f * (g[m] - g[m - 1] + mod)) %= mod;
}
printf("%lld\n", ans);
return 0;
}
标签:Atcoder,横轴,sum,texttt,YY,int,划分,maxn,ARC157D
From: https://www.cnblogs.com/rizynvu/p/18444835