牛客挑战赛55题解

A.铁三角

这题playf哥哥在妄想集合这一题种讲过这个结论，就是斐波那契数列

B.DoubleSum

这一题一看肯定是要使用O(nlogn)的解法，那么我开始想歪了，事实上我们只需要对每个数枚举logn次，对于每一次枚举，统计在mod $c^{k}c^\{k\}$意义下有多少个相同数即可。

对于一个$a_{i}a\_\{i\}$和$a_{j}a\_\{j\}$，题目要我们求出最大的k使得两个数在mod $c^{k}c^\{k\}$的意义下同余，我们可以将题意转换成求解在对于k($0\le k\mathrm{且}{c}^k\le 1e90\; \backslash leq\; k\; 且\; c^\{k\}\; \backslash leq\; 1e9$)，有多少个k满足$a_i,a_j\mathrm{在}mod{c}^{k}a\_\{i\},\; a\_\{j\}在mod\; c^\{k\}$下同余 我还没有想到很好的证明

c.矩阵矩阵距

这题一眼一看就是悬线法 以前没有写过悬线法的题 这题首先要求的就是肯定是要求一个最大的不含零矩阵，但是要满足乘积最大，有0元素的存在，显然是个棘手的问题，那么这题的元素有一个特殊点，就是每个元素都是2的幂，那么我们将每个元素换成其幂次，那么这个问题就转成了求一个最大非零矩阵并且矩阵中的元素之和最大 我们使用h[i][j]这个元素上方最近的0元素到这个点的距离，很显然可以递推

a[i][j] == 0, h[i][j] = 0, 否则，h[i][j] = h[i - 1][j]

以及这个点左边的最近0元素到它的距离，和右边的最近0元素到它的距离，这里我们参考了逆十字带佬的写法，使用一个单调栈，详见代码，剩下就是对每一个点求一个答案并维护最大值了

#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define sz(X) ((int)(X).size())
#define fi first
#define se second
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i ++ ) 
#define per(i, a, n) for (int i = n; i >= a; i -- )
#define endl '\n'
#define IO ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);

using ll = long long;
using i64 = unsigned long long;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll ksm(ll a, ll b, ll c) { ll ans = 1 % c; while (b) { if (b & 1) { ans = 1ll * ans * a % c; } a = 1ll * a * a % c;  b >>= 1; } return ans;}
ll ksc(ll a, ll b, ll c) { int f = ((a >= 0 && b >= 0 || a < 0 && b < 0) ? 1 : -1); ll ans = 0; for (; b; b >>= 1) { if (b & 1) ans = (1ll * ans + a) % c; a = (1ll * a + a) % c; } return ans; }
constexpr int P = 998244353, INF = 0x3f3f3f3f;
constexpr int N = 1010;
int n, m, a[N][N], l[N][N], r[N][N], h[N][N], sum[N][N], ans;

void solve() {
    cin >> n >> m;
    rep(i, 1, n) {
        rep(j, 1, m) {
            cin >> a[i][j];
            if (a[i][j] == 0) {
                a[i][j] = -INF;
            } 
            else a[i][j] = __lg(a[i][j]);
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
        }
    }
    ans = -1;
    function<int(int, int, int, int)> cal = [&](int lx, int rx, int ly, int ry) {
        return sum[rx][ry] - sum[rx][ly] - sum[lx][ry] + sum[lx][ly];
    };
    rep(i, 1, n) {
        vector<int> v = {0};
        rep(j, 1, m) {
            if (a[i][j] == -INF) {
                h[i][j] = 0;
            }
            else {
                h[i][j] = h[i - 1][j] + 1;
            }
            if (h[i][j]) {
                while (h[i][v.back()] >= h[i][j]) v.pop_back();
                l[i][j] = v.back();
            }
            v.push_back(j);
        }
        v.clear();
        v.push_back(m + 1);
        per(j, 1, m) {
            if (h[i][j]) {
                while (h[i][v.back()] >= h[i][j]) v.pop_back();
                r[i][j] = v.back();
                ans = max(ans, {cal(i - h[i][j], i, l[i][j], r[i][j] - 1)});
            }
            v.push_back(j);
        } 
    }
    if (ans < 0) cout << 0 << endl;
    else cout << ksm(2, ans, P) << endl;
}

signed main(void) {
    IO;
	int t;
	t = 1;
	while (t -- ) {
		solve();
	}
    return 0;
}