头像

垫底抽风




离线:6小时前


活动打卡代码 AcWing 3246. 引水入城

#include <cstdio>
#include <cstring>

typedef long long ll;
const int N = 5002;
const ll INF = 1ll << 62;

int n, m, x[N * N << 1];
int r[N][N], c[N][N];
ll d[N], res = INF;

ll min(const ll a, const ll b) {
    return a < b ? a : b;
}

int main()
{
    int a, b, mod;
    scanf("%d%d%d%d%d%d", &n, &m, &a, &b, &mod, x);
    for (int i = 1; i < n * m << 1; ++i) {
        x[i] = ((ll)x[i - 1] * a + b) % mod;
    }
    for (int s = 1, k = 1; s < n; ++s) {
        for (int t = 1; t <= m; ++t, ++k) {
            c[s][t] = x[k];
        }
    }
    for (int s = 2, k = (n - 1) * m + 1; s <= n; ++s) {
        for (int t = 1; t < m; ++t, ++k) {
            r[s][t] = x[k];
        }
    }
    for (int C = 1; C <= m; ++C) {
        for (int i = 1; i < n; ++i) {
            d[i] += c[i][C];
        }
        for (int i = 2; i < n; ++i) {
            d[i] = min(d[i], d[i - 1] + r[i][C]);
        }
        for (int i = n - 2; i; --i) {
            d[i] = min(d[i], d[i + 1] + r[i + 1][C]);
        }
    }
    for (int i = 1; i < n; ++i) {
        res = min(res, d[i]);
    }
    printf("%lld\n", res);
    return 0;
}





题目描述

给定一棵 $n$ 个节点的点权树,$m$ 次查询两点间路径中,所有节点的权值的异或最大值。

输入格式

第一行两个数 $n, m$,表示树的节点数量和查询次数。

第二行 $n$ 个数描述树上每个节点的权值。

接下来 $n - 1$ 行描述树的边。

接下来 $m$ 行每行两个数,表示一个查询。

输出格式

输出共 $m$ 行,表示每次询问的答案。

输入样例:

4 2
11 5 7 9
1 2
1 3
1 4
2 3
1 4

输出样例:

14
11

离线点分治做法不太会,这里给个在线树剖做法。

算法

(树链剖分,ST表,线性基) $O((n + m) \log n \log ^ 2 \max G _ i)$

首先这题要求树上某条链属性,所以想到树剖。

因为树是静态的,所以想到用ST表/Trie。

Trie不太好求任意个元素异或最大值,故想到线性基。

然后这题就做完了

ST表的预处理中,需要将两个线性基合并为一个。考虑如何合并两个线性基。

因为线性基中最多会有 $\log$ 个元素,因此可以枚举其中一个基的所有元素,插入第二个基即可。

这部分代码及注释如下:

const int xbit = 60; // 最多需要的位数
// 线性基
struct vect
{
    ll x[xbit + 1]; // 基中所有元素

    // 辅助函数,返回第 t 个元素
    ll operator[] (const int t) const {return x[t];}

    // 求这组基中异或的最大值
    ll xor_max()
    {
        ll res = 0;
        for (int i = xbit; ~i; i -- )
            if ((res ^ x[i]) > res)
                res ^= x[i];
        return res;
    }

    // 插入一个数 t
    bool add(ll t)
    {
        for (int i = xbit; ~i; i -- )
            if (t >> i & 1)
                if (x[i]) t ^= x[i];
                else
                {
                    x[i] = t;
                    return true;
                }
    }

    // 插入一组基 t
    void add(const vect& t)
    {
        for (int i = xbit; ~i; i -- )
            if (t[i])
                add(t[i]);
    }
};

// 合并两个两个基
vect operator + (vect a, const vect& b)
{
    a.add(b);
    return a;
}

剩下的就是 ST 表和树剖板子了,见代码及注释。

时间复杂度

合并线性基的复杂度是 $O(\log ^ 2 \max G _ i)$。

预处理会合并 $O(n \log n)$ 次,故这部分复杂度是 $O(n \log n \log ^ 2 \max G _ i)$。

每次查询会合并 $O(\log n)$ 次,总共有 $m$ 次查询,故这部分复杂度是 $O(n \log n \log ^ 2 G _ i)$。

故总复杂度为 $O((n + m) \log n \log ^ 2 \max G _ i)$。

C++ 代码

#include <cstdio>
#include <cstring>

typedef long long ll;

const int xbit = 60; // 最多需要的位数
// 线性基
struct vect
{
    ll x[xbit + 1]; // 基中所有元素

    // 辅助函数,返回第 t 个元素
    ll operator[] (const int t) const {return x[t];}

    // 求这组基中异或的最大值
    ll xor_max()
    {
        ll res = 0;
        for (int i = xbit; ~i; i -- )
            if ((res ^ x[i]) > res)
                res ^= x[i];
        return res;
    }

    // 插入一个数 t
    bool add(ll t)
    {
        for (int i = xbit; ~i; i -- )
            if (t >> i & 1)
                if (x[i]) t ^= x[i];
                else
                {
                    x[i] = t;
                    return true;
                }
    }

    // 插入一组基 t
    void add(const vect& t)
    {
        for (int i = xbit; ~i; i -- )
            if (t[i])
                add(t[i]);
    }
};

// 合并两个两个基
vect operator + (vect a, const vect& b)
{
    a.add(b);
    return a;
}

const int N = 20005;
const int M = 400005;

int n, m;
int h[N], e[M], ne[M], idx;
int dep[N], top[N], fa[N], son[N];
int id[N], sz[N], scnt;
ll w[N], nw[N];

struct ST
{
    vect f[N][15];
    int lg2[N];

    // 预处理
    void build()
    {
        memset(f, 0, sizeof f);
        for (int i = 1; 1 << i <= n; i ++ ) lg2[1 << i] = 1;
        for (int i = 1; i <= n; i ++ ) lg2[i] += lg2[i - 1];
        for (int i = 1; i <= n; i ++ ) f[i][0].add(nw[i]);
        for (int k = 0; k < 14; k ++ )
            for (int i = 1; i + (1 << k) <= n; i ++ )
                f[i][k + 1] = f[i][k] + f[i + (1 << k)][k];
    }

    // 查区间 [l, r] 的基
    vect query(int l, int r)
    {
        int len = lg2[r - l + 1];
        return f[l][len] + f[r - (1 << len) + 1][len];
    }
} st;

void add(int a, int b)
{
    e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}

void dfs1(int u, int father, int depth)
{
    fa[u] = father, dep[u] = depth, sz[u] = 1;
    for (int i = h[u]; i; i = ne[i])
        if (e[i] != father)
        {
            dfs1(e[i], u, depth + 1);
            sz[u] += sz[e[i]];
            if (sz[e[i]] > sz[son[u]]) son[u] = e[i];
        }
}

void dfs2(int u, int t)
{
    id[u] = ++ scnt, nw[scnt] = w[u], top[u] = t;
    if (son[u])
    {
        dfs2(son[u], t);
        for (int i = h[u]; i; i = ne[i])
            if (e[i] != son[u] && e[i] != fa[u])
                dfs2(e[i], e[i]);
    }
}

// 查路径 a -> b 节点的权值的异或最大值
ll query(int a, int b)
{
    // res 存该路径中的基
    static vect res;
    memset(res.x, 0, sizeof res.x);
    while (top[a] != top[b])
    {
        if (dep[top[a]] < dep[top[b]]) a ^= b ^= a ^= b;
        res.add(st.query(id[top[a]], id[a]));
        a = fa[top[a]];
    }
    if (dep[a] < dep[b]) a ^= b ^= a ^= b;
    res.add(st.query(id[b], id[a]));
    return res.xor_max();
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", w + i);
    for (int i = 1; i < n; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    dfs1(1, 0, 0);
    dfs2(1, 1);
    st.build();
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%lld\n", query(a, b));
    }
    return 0;
}


新鲜事 原文

图片



线性筛质数

const int N = 1000001;
int primes[N], cnt;
bool st[N];
void init() {
    for (int i = 2; i < N; ++i) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; i * primes[j] < N; ++j) {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

筛法求 $\varphi(x)$

int phi[N];
void init() {
    for (int i = 2; i < N; ++i) {
        if (!st[i]) primes[cnt++] = i, phi[i] = i - 1;
        for (int j = 0; i * primes[j] < N; ++j) {
            st[i * primes[j]] = true;
            if (i % primes[j]) {
                phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            } else {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
        }
    }
}

筛法求 $\mu(x)$

int mu[N];
void init() {
    mu[1] = 1; // 这里一定要记得手动初始化 mu[1]!!QAQ
    for (int i = 2; i < N; ++i) {
        if (!st[i]) primes[cnt++] = i, mu[i] = -1;
        for (int j = 0; i * primes[j] < N; ++j) {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
            mu[i * primes[j]] = -mu[i];
        }
    }
}

筛法求 $d(i) = \sum _ {k | x} 1$

int d[N], g[N];
void init() {
    d[1] = 1;
    for (int i = 2; i < N; ++i) {
        if (!st[i]) primes[cnt++] = i, d[i] = 2, g[i] = 2;
        for (int j = 0; i * primes[j] < N; ++j) {
            st[i * primes[j]] = true;
            if (i % primes[j]) {
                g[i * primes[j]] = 2;
                d[i * primes[j]] = 2 * d[i];
            } else {
                g[i * primes[j]] = g[i] + 1;
                d[i * primes[j]] = d[i] / g[i] * (g[i] + 1);
                break;
            }
        }
    }
}

筛法求 $w(x) = \sum _ {k | x} k$

int w[N], g[N];
void init() {
    w[1] = 1;
    for (int i = 2; i < N; ++i) {
        if (!st[i]) primes[cnt++] = i, w[i] = g[i] = i + 1;
        for (int j = 0; i * primes[j] < N; ++j) {
            st[i * primes[j]] = true;
            if (i % primes[j]) {
                g[i * primes[j]] = primes[j] + 1;
                w[i * primes[j]] = w[i] * (primes[j] + 1);
            } else {
                g[i * primes[j]] = g[i] * primes[j] + 1;
                w[i * primes[j]] = w[i] / g[i] * g[i * primes[j]];
                break;
            }
        }
    }
}

其它的忘了=,=



活动打卡代码 AcWing 449. 质因数分解

$
\texttt{#include }\texttt{<}\texttt{cstdio}\texttt{>}\\
\texttt{int main()}\\
\texttt{\{}\\
\qquad\texttt{int n;}\\
\qquad\texttt{scanf(“%d”,&n);}\\
\qquad\texttt{for(int i=2;;i++)}\\
\qquad\qquad\texttt{if(n%i==0)}\\
\qquad\qquad\texttt{\{}\\
\qquad\qquad\qquad\texttt{printf(“%d\n”,n/i);}\\
\qquad\qquad\qquad\texttt{break;}\\
\qquad\qquad\texttt{\}}\\
\qquad\texttt{return 0;}\\
\texttt{\}}\\
$



活动打卡代码 AcWing 148. 合并果子

$
\texttt{#include }\texttt{<}\texttt{iostream}\texttt{>}\\
\texttt{#include }\texttt{<}\texttt{queue}\texttt{>}\\
\\
\texttt{using namespace std;}\\
\\
\texttt{int n,x;}\\
\\
\texttt{int main()}\\
\texttt{\{}\\
\qquad\texttt{cin}\texttt{>}\texttt{}\texttt{>}\texttt{n;}\\
\qquad\texttt{priority_queue}\texttt{<}\texttt{int,vector}\texttt{<}\texttt{int}\texttt{>}\texttt{,greater}\texttt{<}\texttt{int}\texttt{>}\texttt{}\texttt{>}\texttt{ q;}\\
\qquad\texttt{for(int i=0;i}\texttt{<}\texttt{n;i++)}\\
\qquad\texttt{\{}\\
\qquad\qquad\texttt{cin}\texttt{>}\texttt{}\texttt{>}\texttt{x;}\\
\qquad\qquad\texttt{q.push(x);}\\
\qquad\texttt{\}}\\
\qquad\texttt{int res=0;}\\
\qquad\texttt{while(q.size()}\texttt{>}\texttt{1)}\\
\qquad\texttt{\{}\\
\qquad\qquad\texttt{int a=q.top();q.pop();}\\
\qquad\qquad\texttt{int b=q.top();q.pop();}\\
\qquad\qquad\texttt{res+=a+b,q.push(a+b);}\\
\qquad\texttt{\}}\\
\qquad\texttt{cout}\texttt{<}\texttt{}\texttt{<}\texttt{res}\texttt{<}\texttt{}\texttt{<}\texttt{endl;}\\
\qquad\texttt{return 0;}\\
\texttt{\}}\\
$




题目描述

给定一个 $N \times N$ 的矩阵,你需要求出

  1. 该矩阵中所有子矩阵的 $\texttt{AND}$ 值之和
  2. 该矩阵中所有子矩阵的 $\texttt{OR}$ 值之和

答案对 $10 ^ 9 + 7$ 取模。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行,每行 $N$ 个自然数,描述矩阵。

输出格式

输出两个自然数,分别表示该矩阵的所有子矩阵的 $\texttt{AND}$ 值之和与 $\texttt{OR}$ 值之和,答案对 $10 ^ 9 + 7$ 取模。

数据范围

$1 \leq N \leq 1000$

对于矩阵中的任意一数 $x$,保证 $0 \leq x < 2 ^ {31}$

输入样例1

3
1 0 0
0 0 0
0 0 0

输出样例1

1 9

输入样例2

3
1 2 3
4 5 6
7 8 9

输出样例2

73 314

算法

(位运算,暴力,单调栈,悬线DP) $O(n ^ 2)$

设原矩阵中第 $i$ 行第 $j$ 个元素为 $b _ {i, j}$。

先考虑如何计算 $\texttt{AND}$。

因为矩阵中每个数做多有 $31$ 位,因此我们可以从 $0$ 到 $31$ 枚举每一位。

对于第 $k$ 位,把原矩阵的第 $k$ 位抠出来,得到一个 $01$ 矩阵。

对于该矩阵中任意一个子矩阵,若该子矩阵中所有元素都是 $1$,则该矩阵的 $\texttt{AND}$ 值为 $1$,否则为 $0$。

接下来,问题转化为:给定一个 $01$ 矩阵,求该矩阵中有多少个子矩阵,满足该子矩阵中所有元素都是 $1$。

而子矩阵可以通过两个属性确定:左上角坐标和右下角坐标。

对于这种问题,我们通常的做法是枚举一个属性,然后考虑如何快速求出合法的另一属性数量。 老套路了

本题中,我们可以枚举右下角坐标,考虑如何快速求出有多少个右上角坐标满足条件

这个可以用单调栈求,但不太容易想到。

从上往下依次考虑每一行,假设当前考虑到了第 $k$ 行。

对于第 $k$ 行中第 $k$ 个元素 $b _ {k, i}$,记 $f _ {k, i}$ 表示从该元素开始往上数,有多少个连续的 $1$(包括该元素)。

比如矩阵 $b =
\left[
\begin {matrix}
0 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
\end {matrix}
\right]
$ 时,$f =
\left[
\begin {matrix}
0 & 1 & 1 & 1 & 1 \\
1 & 2 & 2 & 2 & 2 \\
0 & 0 & 0 & 3 & 3 \\
1 & 1 & 1 & 4 & 4 \\
2 & 2 & 2 & 5 & 5 \\
\end {matrix}
\right]
$。

记 $f _ k$ 表示 $f$ 的第 $k$ 行。

则 $f _ k$ 中,包含了所有 $\texttt{AND}$ 值可能为 $1$ 的右下角坐标的信息。

假设我们当前枚举到的右下坐标是 $(k, i)$,考虑此时可取到的左上角的坐标范围。

这个可以 $\text{DP}$,记 $g _ i$ 表示当我们枚举到的右下角坐标为 $(k, i)$ 时,左上角的坐标范围。

设左上角坐标为 $(k - x + 1, y)$。

那么我们可以将状态划分为如下两个集合:

  1. 当 $x = f _ {k, i}$ 时
  2. 剩下的

至于为什么这么划分,是因为当 $x = f _ {k, i}$ 时的部分,可以用单调栈快速计算,这个后面会写到。

考虑当 $x$ 取到 $f _ {k, i}$ 时,$y$ 的取值范围。

因为 $x$ 取到了 $f _ {k, i}$,所以对于任意 $y \leq j \leq i$ 的 $j$ 而言,都有 $f _ {k, j} \geq f _ {k, i}$。

那么能取到的最小的 $y$,就是 $f _ k$ 中从 $i$ 往左数,最后一个的 $\geq f _ {k, i}$ 的数的位置

也就是 $f _ k$ 中从 $i$ 往左数,第一个的 $< f _ {k, i}$ 的数的位置 $ + 1$

记 $l _ i$ 表示第一个的 $< f _ {k, i}$ 的数的位置,那么整个左上角为 $(k - f _ {k, i} + 1, l _ i + 1)$,右下角为 $(k, i)$ 的子矩阵中,所有元素都是 $1$。

我们固定了右下角坐标为 $(k, i)$,而在该子矩阵中,我们可以任取一个位置作为子矩阵左上角,该子矩阵中的元素都是 $1$。

那么当 $x = f _ {k, i}$ 时,对 $g _ i$ 的贡献,即为 $f _ {k, i} \times (i - l _ i)$。

而 $l _ i$ 可以使用单调栈快速计算,这样就可以快速求出当 $x = f _ {k, i}$ 时对 $g _ i$ 的贡献了。

考虑如何计算出剩下的部分。

对于剩下的部分,有 $y \leq l _ i$。

因此剩下的左上角的坐标范围,即为原左上角坐标为 $(k - x + 1, y)$,加上一个 $y \leq l _ i$ 的限制。

不难发现这部分恰好就是 $g _ {l _ i}$,因为当我们考虑以 $(k, l _ i)$ 为右下角坐标的矩阵时,左上角坐标的 $y$ 的范围必然有 $y \leq l _ i$。

那么就得到了转移方程 $g _ i = g _ {l _ i} + f _ {k, i} \times (i - l _ i)$。

这么说可能比较抽象,这里用上述例子中的矩阵 $b _ {5, 5}$ 作为 $(k, i)$ 为例(即 $k = 5, i = 5$ 时)。

当 $k = 5$ 时,$f _ k = [\begin {matrix} 2 & 2 & 2 & 5 & 5 \end {matrix}]$,表示我们当前考虑矩阵 $
\left[
\begin {matrix}
& & & 1 & 1 \\
& & & 1 & 1 \\
& & & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
\end {matrix}
\right]
$。

$i = 5$ 表示我们当前考虑以如下矩阵中,以蓝色位置为右下角的,所有与值为 $1$ 的矩阵 $
\left[
\begin {matrix}
& & & 1 & 1 \\
& & & 1 & 1 \\
& & & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & \color{blue} 1 \\
\end {matrix}
\right]
$。

$f _ {k, i} \times (i - l _ i)$ 表示以下矩阵中红色部分对 $g _ 5$ 的贡献,$g _ {l _ 5 = 3}$ 表示黑色部分对 $g _ 5$ 的贡献。

$
\left[
\begin {matrix}
& & & \color{red} 1 & \color{red} 1 \\
& & & \color{red} 1 & \color{red} 1 \\
& & & \color{red} 1 & \color{red} 1 \\
1 & 1 & 1 & \color{red} 1 & \color{red} 1 \\
1 & 1 & 1 & \color{red} 1 & \color{red} 1 \\
\end {matrix}
\right]
$

这样我们就可以线性计算出所有的 $g$,然后计入答案了。

接下来考虑如何计算 $\texttt{OR}$ 和。

观察 $\texttt{AND}$ 运算和 $\texttt{OR}$ 运算的真值表:

$a$ $b$ $a \texttt{ AND } b$ $a \texttt{ OR } b$
$0$ $0$ $0$ $0$
$0$ $1$ $0$ $1$
$1$ $0$ $0$ $1$
$1$ $1$ $1$ $1$

可以发现,$¬(a \texttt{ OR } b) = ¬a \texttt{ AND } ¬b$。(这个从逻辑上也很好理解啦)

根据这个公式,我们可以先将矩阵中所有元素取反(即异或 $1$),然后计算 $\texttt{AND}$,得到所有 $\texttt{OR}$ 为 $0$ 的子矩阵个数。

再用原矩阵中总共的子矩阵个数,减去 $\texttt{OR}$ 为 $0$ 的子矩阵个数,即可得到 $\texttt{OR}$ 为 $1$ 的子矩阵个数。

考虑一个 $N \times N$ 的矩阵,有多少子矩阵。

对于该矩阵的每个子矩阵,我们可以用左上角坐标和右下角坐标确定。

设两个坐标分别为 $(x _ 1, y _ 1), (x _ 2, y _ 2)$,分别考虑这两个坐标中 $4$ 个元素的取值范围。

对于每个 $x _ 2, y _ 2$,左上角坐标必须满足 $x _ 1 \leq x _ 2, y _ 1 \leq y _ 2$。

那么我们总共的子矩阵个数即为:

$$
\begin {aligned}
& \sum _ {x _ 2 = 1} ^ N \sum _ {y _ 2 = 1} ^ N \sum _ {x _ 1 = 1} ^ {x _ 2} \sum _ {y _ 1 = 1} ^ {y _ 2} 1 \\
= & \sum _ {x _ 2 = 1} ^ N \sum _ {x _ 1 = 1} ^ {x _ 2} \sum _ {y _ 2 = 1} ^ N \sum _ {y _ 1 = 1} ^ {y _ 2} 1 \\
= & (\sum _ {x _ 2 = 1} ^ N \sum _ {x _ 1 = 1} ^ {x _ 2} 1) (\sum _ {y _ 2 = 1} ^ N \sum _ {y _ 1 = 1} ^ {y _ 2} 1) \\
\end {aligned}
$$

这两个式子是完全一样的,因此可化简为

$$
\begin {aligned}
& (\sum _ {i = 1} ^ N \sum _ {j = 1} ^ i 1) ^ 2 \\
= & (\sum _ {i = 1} ^ N i) ^ 2 \\
= & (\frac {N (N + 1)} 2) ^ 2 \\
\end {aligned}
$$

那么我们就用大常数的线性做法解决了这题。

时间复杂度

$O(64n ^ 2) = O(n ^ 2)$。

C++ 代码(不卡常版,只过 $7$ 个点)

#include <cstdio>
#include <cstring>

typedef long long ll;
const int N = 1005;
const int mod = 1e9 + 7;

int n;
int b[N][N];
bool a[N][N];

ll work()
{
    ll res = 0;
    static int stk[N], tt;
    static int f[N], l[N], g[N];
    memset(f, 0, sizeof f);
    for (int k = 1; k <= n; k ++ )
    {
        for (int i = 1; i <= n; i ++ )
            if (a[k][i]) f[i] ++ ;
            else    f[i] = 0;

        tt = 0;
        for (int i = 1; i <= n; i ++ )
        {
            while (tt && f[stk[tt]] >= f[i]) tt -- ;
            l[i] = stk[tt];
            stk[ ++ tt] = i;
        }

        for (int i = 1; i <= n; i ++ )
        {
            g[i] = (f[i] * (i - l[i]) + g[l[i]]) % mod;
            (res += g[i]) %= mod;
        }
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            scanf("%d", b[i] + j);

    ll res = 0;
    for (int k = 0; k < 31; k ++ )
    {
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                a[i][j] = b[i][j] >> k & 1;
        (res += work() << k) %= mod;
    }
    printf("%lld ", res);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            b[i][j] ^= 0x7fffffff;

    res = 0;
    for (int k = 0; k < 31; k ++ )
    {
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                a[i][j] = b[i][j] >> k & 1;
        (res += ((n * n * (n + 1ll) * (n + 1ll) / 4 - work()) % mod << k) % mod) %= mod;
    }
    printf("%lld\n", res);

    return 0;
}


关于卡常:

$a$ 不开了,直接在 work 中求第 $x$ 位。

$l$ 数组可以去掉,在处理单调栈时做 $\text{DP}$ 并计算答案。

读入数据量较多,scanf 改为快读。

将所有 i ++ 类自增运算改为 ++ i

卡常后 C++ 代码(可 AC)

#include <cstdio>
#include <cstring>

typedef long long ll;
const int N = 1005;
const int mod = 1e9 + 7;

int n;
int b[N][N];

inline int read()
{
    int x = 0; char c = getchar();
    while (~c && (c < 48 || c > 57)) c = getchar();
    for (; c > 47 && c < 58; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return x;
}

ll work(int x)
{
    ll res = 0;
    static int stk[N], tt;
    static int f[N], g[N];
    memset(f, 0, sizeof f);
    for (int k = 1; k <= n; ++ k)
    {
        for (int i = 1; i <= n; ++ i)
            if (b[k][i] >> x & 1) ++ f[i];
            else    f[i] = 0;

        tt = 0;
        for (int i = 1; i <= n; ++ i)
        {
            while (tt && f[stk[tt]] >= f[i]) -- tt;
            g[i] = f[i] * (i - stk[tt]) + g[stk[tt]];
            (res += g[i]) %= mod;
            stk[ ++ tt] = i;
        }
    }
    return res;
}

int main()
{
    n = read();
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            b[i][j] = read();

    ll res = 0;
    for (int k = 0; k < 31; ++ k)
        (res += work(k) << k) %= mod;
    printf("%lld ", res);

    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            b[i][j] ^= 0x7fffffff;

    res = 0;
    for (int k = 0; k < 31; ++ k)
        (res += (n * n * (n + 1ll) * (n + 1ll) / 4 - work(k)) % mod << k) %= mod;
    printf("%lld\n", res);

    return 0;
}


$$ $$



新鲜事 原文

过年惹,感谢acwing各位网友对我的支持,感谢acwing陪我走过这两年。 祝大家2021万事如意,AC不WA不TLE,Always ACing!!


活动打卡代码 AcWing 441. 数字统计

$
\texttt{#include }\texttt{<}\texttt{cstdio}\texttt{>}\\
\texttt{int a,b,res;}\\
\texttt{int main()}\\
\texttt{\{}\\
\qquad\texttt{scanf(“%d%d”,&a,&b);}\\
\qquad\texttt{for(int i=a;i}\texttt{<}\texttt{=b;i++)}\\
\qquad\qquad\texttt{for(int j=i;j;j/=10)}\\
\qquad\qquad\qquad\texttt{res+=j%10==2;}\\
\qquad\texttt{printf(“%d\n”,res);}\\
\qquad\texttt{return 0;}\\
\texttt{\}}\\
$



活动打卡代码 AcWing 496. 机器翻译

$
\texttt{#include }\texttt{<}\texttt{cstdio}\texttt{>}\\
\texttt{#include }\texttt{<}\texttt{cstring}\texttt{>}\\
\texttt{const int N=1005;}\\
\texttt{int n,m,res;}\\
\texttt{int q[N],hh,tt;}\\
\texttt{bool st[N];}\\
\texttt{int main()}\\
\texttt{\{}\\
\qquad\texttt{scanf(“%d%d”,&m,&n);}\\
\qquad\texttt{while(n–)}\\
\qquad\texttt{\{}\\
\qquad\qquad\texttt{int x;}\\
\qquad\qquad\texttt{scanf(“%d”,&x);}\\
\qquad\qquad\texttt{if(!st[x])}\\
\qquad\qquad\texttt{\{}\\
\qquad\qquad\qquad\texttt{res++;}\\
\qquad\qquad\qquad\texttt{if(tt-hh==m)st[q[hh++]]=false;}\\
\qquad\qquad\qquad\texttt{q[tt++]=x,st[x]=true;}\\
\qquad\qquad\texttt{\}}\\
\qquad\texttt{\}}\\
\qquad\texttt{printf(“%d\n”,res);}\\
\qquad\texttt{return 0;}\\
\texttt{\}}\\
$