NC17383 A Simple Problem with Integers

这篇具有很好参考价值的文章主要介绍了NC17383 A Simple Problem with Integers。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目链接

题目

题目描述

You have N integers A1, A2, ... , AN. You are asked to write a program to receive and execute two kinds of instructions:

  1. C a b means performing \(A_i = A_i^2 \mod 2018\) for all Ai such that a ≤ i ≤ b.
  2. Q a b means query the sum of Aa, Aa+1, ..., Ab. Note that the sum is not taken modulo 2018.

输入描述

The first line of the input is T(1≤ T ≤ 20), which stands for the number of test cases you need to solve.
The first line of each test case contains N (1 ≤ N ≤ 50000).The second line contains N numbers, the initial values of A1, A2, ..., An. 0 ≤ Ai < 2018. The third line contains the number of operations Q (0 ≤ Q ≤ 50000). The following Q lines represents an operation having the format "C a b" or "Q a b", which has been described above. 1 ≤ a ≤ b ≤ N.

输出描述

For each test case, print a line "Case #t:" (without quotes, t means the index of the test case) at the beginning.
You need to answer all Q commands in order. One answer in a line.

示例1

输入

1
8
17 239 17 239 50 234 478 43
10
Q 2 6
C 2 7
C 3 4
Q 4 7
C 5 8
Q 6 7
C 1 8
Q 2 5
Q 3 4
Q 1 8

输出

Case #1:
779
2507
952
6749
3486
9937

题解

知识点:线段树,数论。

显然,区间同余是没法直接运用懒标记的,我们需要找到能使用懒标记的结构。

容易证明, \(A_i = A_i^2 \mod 2018\) 运算在有限次操作后一定会进入一个循环节,且长度的最小公倍数不超过 \(6\) 。而且可以发现,进入循环的需要的操作次数其实很少。

注意到,进入循环的区间可以预处理出所在循环节的所有值,并用一个指针指向当前值即可,随后每次修改相当于在环上移动指针,显然可以懒标记。对于未进入循环节的区间,先采用单点修改,直到其值进入循环节。

因此,我们先预处理枚举 \([0,2018)\) 所有数是否在循环节内,用 \(cyc\) 数组记录每个数的所在循环节的长度。如果某数的循环节长度非 \(0\) ,则其为循环节的一部分。我们对循环节长度取最小公倍数 \(cyclcm\),以便统一管理。

对此,区间信息需要维护区间是否进入循环 \(lp\) 、区间循环值 \(sum\) 数组、区间值指针 \(pos\) 。若未进入循环,则值存 \(sum[0]\) ,且 \(pos = 0\) ;若进入循环,则 \(sum\) 存循环的各个值, \(pos\) 指向当前值的位置。

区间合并,有两种情况:

  1. 存在子区间未进入循环,则区间未进入循环,最终值由子区间当前值相加。
  2. 子区间都进入循环,则区间进入循环,顺序遍历子区间对应的循环值,并将和更新到区间的 \(sum\)

区间修改只需要维护指针平移总量 \(cnt\)

区间修改,有两种情况:

  1. 区间未进入循环,则继续递归子区间,直到单点修改。每次单点修改后,检查是否进入循环,若进入循环,则预处理出 \(sum\)
  2. 区间已进入循环,则直接平移 \(pos\) 即可。

标记修改,直接加到标记上即可,可以模 \(2018\)。注意,当且仅当区间进入循环后标记才有意义,但事实上,未进入循环的区间标签始终为 \(0\) ,对修改没有影响,无需特判。

这道题实际上是洛谷P4681的弱化版,我这里使用了通解的做法,比只针对这道题的做法要慢一点。只针对这道题的做法是基于另一个更进一步的结论,所有数字在 \(6\) 次操作之后一定进入循环,那么只需要记录一个单点是否操作 \(6\) 次作为检查条件即可,省去了枚举 \([0,2018)\) 所有数字的循环节长度的时间。

时间复杂度 \(O((n+m) \ log n)\)

空间复杂度 \(O(n)\)文章来源地址https://www.toymoban.com/news/detail-430345.html

代码

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

const int P = 2018;
int cyc[P];
int cyclcm;

void init_cyc() {
    cyclcm = 1;
    for (int i = 0;i < P;i++) {
        cyc[i] = 0;
        vector<int> vis(P);
        for (int j = 1, x = i;;j++, x = x * x % P) {
            if (vis[x]) {
                if (x == i) {
                    cyc[i] = j - vis[i];
                    cyclcm = lcm(cyclcm, cyc[i]);
                }
                break;
            }
            vis[x] = j;
        }
    }
}

class SegmentTreeLazy {
    struct T {
        array<int, 6> sum;
        int pos;
        bool lp;
    };
    struct F {
        int cnt;
    };
    int n;
    vector<T> node;
    vector<F> lazy;

    void push_up(int rt) {
        node[rt].lp = node[rt << 1].lp && node[rt << 1 | 1].lp;
        node[rt].pos = 0;
        if (node[rt].lp)
            for (int i = 0, l = node[rt << 1].pos, r = node[rt << 1 | 1].pos;
                i < cyclcm;
                i++, ++l %= cyclcm, ++r %= cyclcm)
                node[rt].sum[i] = node[rt << 1].sum[l] + node[rt << 1 | 1].sum[r];
        else node[rt].sum[0] = node[rt << 1].sum[node[rt << 1].pos] + node[rt << 1 | 1].sum[node[rt << 1 | 1].pos];
    }

    void push_down(int rt) {
        (node[rt << 1].pos += lazy[rt].cnt) %= cyclcm;
        (lazy[rt << 1].cnt += lazy[rt].cnt) %= cyclcm;
        (node[rt << 1 | 1].pos += lazy[rt].cnt) %= cyclcm;
        (lazy[rt << 1 | 1].cnt += lazy[rt].cnt) %= cyclcm;
        lazy[rt].cnt = 0;
    }

    void check(int rt) {
        node[rt].pos = 0;
        if (cyc[node[rt].sum[0]]) {
            node[rt].lp = 1;
            for (int i = 1;i < cyclcm;i++)
                node[rt].sum[i] = node[rt].sum[i - 1] * node[rt].sum[i - 1] % P;
        }
        else node[rt].lp = 0;
    }

    void update(int rt, int l, int r, int x, int y) {
        if (r < x || y < l) return;
        if (x <= l && r <= y && node[rt].lp) {
            ++node[rt].pos %= cyclcm;
            ++lazy[rt].cnt %= cyclcm;
            return;
        }
        if (l == r) {
            node[rt].sum[0] = node[rt].sum[0] * node[rt].sum[0] % P;
            check(rt);
            return;
        }
        push_down(rt);
        int mid = l + r >> 1;
        update(rt << 1, l, mid, x, y);
        update(rt << 1 | 1, mid + 1, r, x, y);
        push_up(rt);
    }

    int query(int rt, int l, int r, int x, int y) {
        if (r < x || y < l) return 0;
        if (x <= l && r <= y) return node[rt].sum[node[rt].pos];
        push_down(rt);
        int mid = l + r >> 1;
        return query(rt << 1, l, mid, x, y) + query(rt << 1 | 1, mid + 1, r, x, y);
    }

public:
    SegmentTreeLazy(const vector<int> &src) { init(src); }

    void init(const vector<int> &src) {
        assert(src.size() >= 2);
        n = src.size() - 1;
        node.assign(n << 2, { {},0,0 });
        lazy.assign(n << 2, { 0 });
        function<void(int, int, int)> build = [&](int rt, int l, int r) {
            if (l == r) {
                node[rt].sum[0] = src[l];
                check(rt);
                return;
            }
            int mid = l + r >> 1;
            build(rt << 1, l, mid);
            build(rt << 1 | 1, mid + 1, r);
            push_up(rt);
        };
        build(1, 1, n);
    }

    void update(int x, int y) { update(1, 1, n, x, y); }

    int query(int x, int y) { return query(1, 1, n, x, y); }
};
//* 朴素操作开销太大(array复制),因此全部展开

bool solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++) cin >> a[i];

    init_cyc();
    SegmentTreeLazy sgt(a);

    int m;
    cin >> m;
    while (m--) {
        char op;
        int l, r;
        cin >> op >> l >> r;
        if (op == 'C') sgt.update(l, r);
        else cout << sgt.query(l, r) << '\n';
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    for (int i = 1;i <= t;i++) {
        cout << "Case #" << i << ":" << '\n';
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

到了这里,关于NC17383 A Simple Problem with Integers的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • pip安装报错Could not fetch URL https://pypi.org/simple/xx/: There was a problem confirming the ssl c

    只是个记录帖):今天使用pip指令安装django时报错: Could not fetch URL https://pypi.org/simple/django/: There was a problem confirming the ssl certificate: HTTPSConnectionPool(host=\\\'pypi.org\\\', port=443): Max retries exceeded with url: /simple/django/ (Caused by SSLError(SSLEOFError(8, \\\'EOF occurred in violation of protocol (_ssl.c:1129)\\\'))

    2024年02月08日
    浏览(46)
  • Tree of Thoughts: Deliberate Problem Solving with Large Language Models

    本文是LLM系列的文章,针对《Tree of Thoughts: Deliberate Problem Solving with Large Language Models》的翻译。 语言模型越来越多地被部署用于解决各种任务中的一般问题,但在推理过程中仍然局限于token级别的从左到右的决策过程。这意味着他们可能无法完成需要探索、战略前瞻或初始决

    2024年02月11日
    浏览(52)
  • A Simple Framework for 3D Lensless Imaging with Programmablle Masks 论文代码部分

    1.1 data数据 net 在这里插入图片描述 2.1 代码整体介绍 这段代码的作用是加载PSFs数据,并进行一系列参数设置。 首先,通过设置 data_dir 变量为数据目录的路径。然后,根据场景名来选择特定于场景的参数。根据不同的场景名,设置 d1 和 d2 的值。 net 场景包括一个距离相机约

    2024年04月10日
    浏览(42)
  • 【论文阅读】(2013)Exact algorithms for the bin packing problem with fragile objects

    论文来源:(2013)Exact algorithms for the bin packing problem with fragile objects 作者:Manuel A. Alba Martínez 等人 我们得到了一组物体,每个物体都具有重量和易碎性,以及大量没有容量的垃圾箱。 我们的目标是找到装满所有物体所需的最少垃圾箱数量,使每个垃圾箱中物体重量的总和小

    2024年02月11日
    浏览(44)
  • 开源项目运行时报错A problem was found with the configuration of task ‘:app:checkDebugManifest‘

    下载开源项目后,对gradle-wrapper.properties中的gradle版本进行了升级,造成了如下问题: 1: Task failed with an exception. ----------- * What went wrong: A problem was found with the configuration of task \\\':app:checkDebugManifest\\\' (type \\\'CheckManifest\\\').   - Type \\\'com.android.build.gradle.internal.tasks.CheckManifest\\\' property \\\'manif

    2023年04月08日
    浏览(34)
  • 已解决note: This error originates from a subprocess,and is likely not a problem with pip.

    已解决(pip安装第三方模块lxml模块报错)Building wheels for collected packages: lxml Building wheel for lxml (setup.py) … error error: subprocess-exited-with-error python setup.py bdist_wheel did not run successfully. note: This error originates from a subprocess,and is likely not a problem with pip. ERROR: Failed building wheel for lxml n

    2024年01月18日
    浏览(41)
  • pip安装库时报错:This error originates from a subprocess, and is likely not a problem with pip.

    前言 一 二、使用步骤 1.引入库 2.读入数据 总结   安装库时出现以下报错 查看要安装的库的版本: 我的python版本3.10所以安了mayavi的最高的版本  successful

    2024年02月11日
    浏览(46)
  • 王道机试指南(第二版)——题目OJ链接

    王道机试指南(第二版)——题目OJ链接 方便大家跳转检验,侵删。 题目 地址 例题2.1 abc(清华大学复试上机题) 例题2.2 反序数(清华大学复试上机题) 例题2.3 对称平方数1(清华大学复试上机题) 习题2.1 与7无关的数(北京大学复试上机题) 习题2.2 百鸡问题(北京哈尔

    2024年01月17日
    浏览(47)
  • 长春理工大学第六届CTF网络攻防大赛题解(文末有题目下载链接)

    此题解仅为部分题解,包括: 【RE】:①Reverse_Checkin ②SimplePE ③EzGame 【Web】①f12 ②ezrunner 【Crypto】①MD5 ②password ③看我回旋踢 ④摩丝 【Misc】①爆爆爆爆 ②凯撒大帝的三个秘密 ③你才是职业选手 ① Reverse Checkin: 双击文件看到如上提示:“也许你能从字符串里找到什么”

    2024年02月05日
    浏览(66)
  • 链接KAFKA异常:Authentication failed during authentication due to invalid credentials with SASL mechanism

    使用带kerberos 认证的Kafka客户端链接kafka 创建topic 出现如下异常:Authentication failed during authentication due to invalid credentials with SASL mechanism。kafka server 后台只有如下异常信息: 开始排查问题原因: 通过查看Kafka源代码定位到错误大致发生在: 大概是在  saslServer.evaluateResponse 的时

    2024年02月11日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包