首页 > 其他分享 >CW高中-C443D

CW高中-C443D

时间:2023-12-24 20:56:06浏览次数:33  
标签:return log seq 高中 int res C443D CW mod

CW高中-C443D

维护下列操作:

  • \(\forall i \in [l,r]:a_i \leftarrow x^{a_i}\)。
  • 求 \(\sum_{i=l}^ra_i \mod M\)。

\(n,q,M,a_i \le 10^5\)。

显然要欧拉定理降幂。(结果考场上别的都想出来了,但不知道不互质的情况解决办法,真的菜死了)

不互质的情况:

\[\begin{aligned} & a^q \equiv a^{q \; \mathrm{mod} \; \varphi (p) + \varphi (p)} \mod p & q\ge \varphi (p) \end{aligned} \]

考虑到每次 \(x \leftarrow \varphi (x)\)。这样的操作到 \(x=1\) 只需要 \(O(\log_2 M)\) 次。

所以会发现一段区间如果被同样的修改操作执行 \(O(\log_2 M)\) 次就会全部相同。

那么考虑相同的区间一起处理。

再势能分析一下,考虑每次修改操作会使得区间内部每个位置的势能 \(-1\),然后使区间两端的势能 \(\leftarrow \log_2M\)。

这样总共是 \(O(n\log_2M+q\log_2M)\)。

所以可以用一个数据结构维护区间,同时维护一颗线段树支持区间赋值和以及区间和查询。

但是每次遍历区间内的幂塔还要快速幂会花掉一个 \(\log_2 M\) 级别的时间,很亏。

所以考虑 \(O(M\sqrt{M})\) 预处理幂。注意应该同时记录取模之前的值是否大于等于当前考虑的模数。

总的时间复杂度为 \(O((n+q)\log_2^2M+M\sqrt{M})\)。实测常数很大。

#include <bits/stdc++.h>
using namespace std;
inline int read (){
    int p = 0;
    char c = getchar ();
    while (c < '0' || c > '9')
        c = getchar ();
    while (c >= '0' && c <= '9'){
        p = (p << 1) + (p << 3) + (c - '0');
        c = getchar ();
    }
    return p;
}
inline void Write (int x){
    if (x > 9)
        Write (x / 10);
    putchar (x % 10 + '0');
}
const int N = 1e5 + 5;
int n, m, mod[25];
int len, T[25];
vector < vector < int > > pw[25], ppw[25];
// because ex-euler theory , have to do a special mul in power-init time.
// Node-Init ---------- start
inline int mul (int a, int b, int d){
    long long res = 1ll * (a >> 1) * (b >> 1);
    return ((res % mod[d]) << 1) | (a & 1) | (b & 1) | (res >= mod[d]);
}
inline int Phi (int x){
    int res = x;
    for (int i = 2;i * i <= x;++ i)
        if (x % i == 0){
            res = res / i * (i - 1);
            while (x % i == 0)
                x /= i;
        }
    if (x > 1)
        res = res / x * (x - 1);
    return res;
}
inline void Init (int p, int u){
    if (p == 1)
        return ;
    len = u;
    mod[u] = p;
    int nex = Phi (p);
    T[u] = sqrt (p);
    while (T[u] * T[u] <= (nex << 1))
        ++ T[u];
    pw[u].resize (p);
    ppw[u].resize (p);
    for (int i = 0;i < p;++ i){
        vector < int > &op = pw[u][i], &opp = ppw[u][i];
        op.resize (T[u] + 1);
        opp.resize (T[u] + 1);
        op[0] = opp[0] = 2;
        for (int j = 1;j <= T[u];++ j)
            op[j] = mul (op[j - 1], i << 1, u);
        for (int j = 1;j <= T[u];++ j)
            opp[j] = mul (opp[j - 1], op[T[u]], u);
    }
    Init (nex, u + 1);
}
inline int Qpow (int a, int p, int d){
    return mul (ppw[d][a][p / T[d]], pw[d][a][p % T[d]], d);
}
struct node {
    int v[25], cnt;
    node (int X = 0, int ap = 0){
        v[0] = X;
        for (int i = 1;i <= len;++ i)
            v[i] = 1;
        cnt = ap;
    }
    void Update (int x){
        for (int i = len;i >= 1;-- i)
            v[i] = v[i - 1];
        v[0] = x;
    }
    int Query (){
        int res = 1;
        for (int i = len;i >= 0;-- i){
            int u = Qpow (v[i] % mod[i], res, i);
            if ((u & 1) || (v[i] >= mod[i] && res != 0))
                res = (u >> 1) + mod[i];
            else
                res = u >> 1;
        }
        return res % mod[0];
    }
};
// Node-Init ---------- end
// Segment_Tree-Init ---------- start
#define lson(p) (p << 1)
#define rson(p) (p << 1 | 1)
struct Segment_tree {
    int l, r;
    long long res;
    int tag;
    bool flg;
    Segment_tree (int L = 0, int R = 0, long long RES = 0, int TAG = 0, bool FLG = false){
        l = L;
        r = R;
        res = RES;
        tag = TAG;
        flg = FLG;
    }
} tr[N << 2];
inline void put_tag (int p, int x){
    tr[p].res = 1ll * (tr[p].r - tr[p].l + 1) * x;
    tr[p].tag = x;
    tr[p].flg = true;
}
inline void push_down (int p){
    if (tr[p].flg){
        tr[p].flg = false;
        put_tag (lson (p), tr[p].tag);
        put_tag (rson (p), tr[p].tag);
    }
}
inline void push_up (int p){
    tr[p].res = tr[lson (p)].res + tr[rson (p)].res;
}
inline void Build (int p, int l, int r){
    tr[p] = Segment_tree (l, r, 0, 0);
    if (l == r)
        return ;
    int mid = (l + r) >> 1;
    Build (lson (p), l, mid);
    Build (rson (p), mid + 1, r);
}
inline void Update (int p, int l, int r, int x){
    if (l <= tr[p].l && tr[p].r <= r){
        put_tag (p, x);
        return ;
    }
    push_down (p);
    int mid = (tr[p].l + tr[p].r) >> 1;
    if (l <= mid)
        Update (lson (p), l, r, x);
    if (r > mid)
        Update (rson (p), l, r, x);
    push_up (p);
}
inline long long Query (int p, int l, int r){
    if (l <= tr[p].l && tr[p].r <= r)
        return tr[p].res;
    push_down (p);
    int mid = (tr[p].l + tr[p].r) >> 1;
    long long sum = 0;
    if (l <= mid)
        sum += Query (lson (p), l, r);
    if (r > mid)
        sum += Query (rson (p), l, r);
    return sum;
}
// Segment_Tree-Init ---------- end
map < int , node > seq;
signed main (){
    // freopen ("research.in", "r", stdin);
    // freopen ("research.out", "w", stdout);
    n = read ();
    m = read ();
    mod[0] = read ();
    Init (mod[0], 0);
    Build (1, 1, n);
    seq[0] = node (0, len);
    for (int i = 1, x;i <= n;++ i){
        x = read ();
        seq.insert (make_pair (i, node (x, len)));
        Update (1, i, i, x);
    }
    while (m --){
        int opt = read (), l = read (), r = read ();
        if (opt == 1){
            int x = read ();
            if (seq.find (l - 1) == seq.end ())
                seq[l - 1] = seq.lower_bound (l)->second;
            seq[l - 1].cnt = len;
            if (seq.find (r) == seq.end ())
                seq[r] = seq.lower_bound (r)->second;
            seq[r].cnt = len;
            for (auto it = seq.lower_bound (l);it->first < r;){
                auto nex = it;
                ++ nex;
                -- it->second.cnt;
                if (it->second.cnt < 0)
                    seq.erase (it);
                it = nex;
            }
            int ll = l;
            for (auto it = seq.lower_bound (l);it != seq.end () && it->first <= r;++ it){
                it->second.Update (x);
                Update (1, ll, it->first, it->second.Query ());
                ll = it->first + 1;
            }
        } else {
            Write (Query (1, l, r) % mod[0]);
            puts ("");
        }
    }
    return 0;
}

标签:return,log,seq,高中,int,res,C443D,CW,mod
From: https://www.cnblogs.com/imcaigou/p/17924846.html

相关文章

  • Acwing.第135场周赛
    比赛地址A.买苹果题目思路:简单的模拟一下就好了代码:#include<bits/stdc++.h>usingnamespacestd;voidsolve(){ intn,x; cin>>n>>x; cout<<n/x<<endl; return; }intmain(){ intt=1; while(t--){ solve(); } return0;}B.牛群题目思路:也......
  • 【Hikari】浙江省高中信息技术系列
    因Hikari官网处于内测状态,暂无法访问,Hikari浙江省高中信息技术系列暂时以本博客单独放置课程列表(按时间顺序排序)课程课程内容视频及笔记算法第一讲(一)——桶排序介绍了桶排序的基本原理及其基本用法视频(Bilibili):「十分钟一个知识点」桶排序、笔记(蓝奏云):算法第......
  • 一些高中解析几何的通解
    最近学解析几何,发现很多题可以直接套通解,于是把通解求了个遍。点和点求\(P_1(x_1,y_1)\)、\(P_2(x_2,y_2)\)所在的直线\(\left(y_{2}-y_{1}\right)x+\left(x_{1}-x_{2}\right)y+x_{2}y_{1}-x_{1}y_{2}=0\)https://www.desmos.com/calculator/tzjl5dpoi1求\(P_1(x_1......
  • CWOI DS 专题 2
    怎么又开一个ds专题啊/yunA-如何正确地排序以前写的,把以前写的题解贺过来。正难则反,总贡献减去不会成为\(\min/\max\)的数。\(B_i+B_j\)不会产生贡献的条件就是存在\(A_i+A_j,C_i+C_j\)满足\(\begin{cases}A_i+A_j\leB_i+B_j\\B_i+B_j\leC_i+C_j\end{cases}\),移项......
  • 南阳第一批次高中
    南阳第一批次高中如下:南阳市一中、南阳市五中、油田一中、南阳市二中、南阳市八中、南阳市第一完全学校高中部、南阳市第二完全学校高中部、南阳市第三完全学校高中部(纳入市二中招生计划)、南阳市第四完全学校高中部、南阳市第五完全学校高中部、南阳市第九完全学校高中部、南阳市......
  • 【拜谢tgt】浅谈微积分在高中数学中的应用
    pdf版本(渲染较好)浅谈微积分在高中数学中的应用前言本文仅作为各类题型或技巧的归纳,以在高考中应用为目的。A\(\operatorname{L'H\hatopital's\;rule}\)不严格地说,洛必达法则就是在\(\frac{0}{0}\)型和\(\frac{\infty}{\infty}\)型时,有:\[\begin{aligned}\lim_{x\t......
  • 一道很不错的高中数学题的题解解析
    引:上周六上午把一道高中的数学竞赛题(一道8分的填空题,原题如下图所示)当成一道大题(如上)郑重其事地和孩子以互动的方式探讨了这个题的题解分析. 这是一道出得很好的题.其题解所涉及的知识不超出高一目前所学内容,因此高一的学生也是可能做得出来的.但这题是一道很综合的题,涉......
  • Acwing.第134场周赛
    Acwing.第134场周赛比赛地址A排序题目思路:简单的模拟代码:#include<bits/stdc++.h>usingnamespacestd;voidsolve(){ inta,b,c; cin>>a>>b>>c; intans=a+b+c; intmaxn=max(a,max(b,c)); intminn=min(a,min(b,c)); cout<<minn<<"......
  • 基于CW32F030单片机的便携式多功能测试笔
    一、产品背景在日常的硬件调试工作中,我们最常使用的仪器仪表可能就是万用表了,虽然万用表号称“万用”,但大部分时候,我们需要使用到的功能无非是电压测量和通断测量。作为调试的“得力干将”,万用表有时候也会存在一些缺点和局限性,比如:体积较大不便于携带、无法直接反应逻辑电平情况而......
  • Acwing秋季每日一题补题---搜索字符串
    搜索字符串题目链接思路:字符串哈希+滑动窗口当然因为符合题意的子串会重复,所以我们要考虑去重的问题代码:#include<bits/stdc++.h>usingnamespacestd;#defineintunsignedlonglongconstintN=2e5+10;constintP=131;chara[N],b[N];//字符串intcnt[26];//统......