CCF计算机软件能力认证试题练习：201912-5 魔数

前置知识：BFS，线段树等

(f(x) = (x\%A)\%B)

这个函数值的和直接用线段树维护是不太行的（也可能是我不知道），后来想了很久的取模技巧操作...但是越想越远根本不着边际

网上也找不到题解，就去大佬群里面求助，cls一两句话就解决了这道题...

这几个U随便乘，最后只会有不到40个本质不同的数字

关于这个结论是如何得到的，不清楚，但是是很容易验证的，代码如下：
由于数字刚好不超过无符号longlong的范围，所以可以用快速乘来解决(复杂度log)，算法类似于快速幂，如果没有了解过的同学可以去学一下

ull U[5] = {
    314882150829468584,
    427197303358170108,
    1022292690726729920,
    1698479428772363217,
    2006101093849356424
};
ull mod = 2009731336725594113;
unordered_map<ull, int> mp;
ull f[35],a[N][35];
int g[35][35];
ull mul(ull a, ull b){
    ull res = 0;
    for(;b;b>>=1){
        if(b & 1) res = (res + a) % mod;
        a = (a + a) % mod;
    }
    return res;
}
void getConvert(){
    queue<ull> q;
    int id = 1;
    for(int i=0;i<5;i++)q.push(U[i]), mp[U[i]] = id++;
    //BFS找到所有可能的结果
    while(q.size()){
        ull x = q.front();q.pop();
        f[mp[x]] = x;
        for(int i=0;i<5;i++){
            ull t = mul(x, U[i]);
            if(mp[t]) {
                continue;   
            }
            mp[t] = id++;
            q.push(t);
        }
    }
    // 得到转移函数
    for(int i=1;i<=32;i++){
        for(int j=i;j<=32;j++){
            g[i][j] = g[j][i] = mp[mul(f[i], f[j])];
        }
    }
}

然后该怎么解决？线段树维护区间乘这32种数字的结果和。
因为不管怎么乘，最终结果只会对应乘的是这32个数字中的某一个。

对于线段树上的某个节点，(s[i]) 表示区间内每个数乘了第 i 个数字即 (f[i]) 后模2019的和。

对于每次修改，假如要乘第 (f[i]) 个数字，那么对于 (j in [1,32], s[j] = s[g[j][i]]) g数组的含义见上述代码，也就是本来这个区间都乘了 (f[j])，然后又乘了个 (f[i])，那么最终就会发生转移，相当于乘第 (g[j][i]) 个数字，对应于原来的 (s[g[j][i]])

然后区间要打标记，如果之前没有标记过，那么 (tag = i) 表示当前乘了第 i 个数字，否则(tag = g[tag][i])进行转移

线段树上面的具体操作就是这样，但是我兴高采烈的写完就交了上去，一直T到怀疑人生。

初始化线段树节点只有 2n 个，每个初始化32次，复杂度根本不会炸

每次查询是 (32log n) ，总共1e5次查询，也不会炸，那是为什么呢？

实在没办法了，输入了个1000000 100000试了试...发现大概用了二十秒才初始化结束。突然顿悟原来这里还有个log的操作在做鬼

void build(int p, int l, int r){
    t[p].l = l;t[p].r = r;
    if(l == r){
        for(int i=1;i<=32;i++){
            //这一句复杂度是(log2e18),大概是60
            //即使反过来换成mul(f[i],l)，也会有20左右的大小，根本无法承受
            t[p].s[i] = mul(l, f[i]) % 2019;
        }
        t[p].res = t[p].s[28];
        t[p].tag = 0;
        return;
    }
    int mid = l + r >> 1;
    build(p*2, l, mid);
    build(p*2+1, mid+1, r);
    for(int i=1;i<=32;i++){
        t[p].s[i] = t[p*2].s[i] + t[p*2+1].s[i];
    }
    t[p].res = t[p].s[28];
    t[p].tag = 0;
}

好了，这次应该知道怎么优化了，题目数据给出 A 序列初值为 1...n 也是有道理的，否则这里的复杂度怎么也优化不掉的

总时间复杂度(O(32n+32qlog n))

AC截图

这个时限(4s)，空间(1G)，感觉真是刚刚好

下面是AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
#define dbg(x...) do { cout << "33[32;1m" << #x <<" -> "; err(x); } while (0)
void err() { cout << "33[39;0m" << endl; }
template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); }
typedef unsigned long long ull;
const int N = 1000010;
ull U[5] = {
    314882150829468584,
    427197303358170108,
    1022292690726729920,
    1698479428772363217,
    2006101093849356424
};
ull mod = 2009731336725594113;
unordered_map<ull, int> mp;
ull f[35],a[N][35];
int g[35][35];
ull mul(ull a, ull b){
    ull res = 0;
    for(;b;b>>=1){
        if(b & 1) res = (res + a) % mod;
        a = (a + a) % mod;
    }
    return res;
}
void getConvert(){
    queue<ull> q;
    int id = 1;
    for(int i=0;i<5;i++)q.push(U[i]), mp[U[i]] = id++;
    while(q.size()){
        ull x = q.front();q.pop();
        f[mp[x]] = x;
        for(int i=0;i<5;i++){
            ull t = mul(x, U[i]);
            if(mp[t]) {
                continue;   
            }
            mp[t] = id++;
            q.push(t);
        }
    }
    for(int i=1;i<=32;i++){
        for(int j=i;j<=32;j++){
            g[i][j] = g[j][i] = mp[mul(f[i], f[j])];
        }
    }
}
int tmp[33];
int n, q;
struct SegTree{
    int l,r;
    int s[33];//维护它，但是它后期可能还会变
    int res;
    int tag;
    // 转移函数，target表示乘 f[target]
    void convert(int target){
        for(int i=1;i<=32;i++){
            tmp[i] = s[g[i][target]];
        }
        for(int i=1;i<=32;i++){
            s[i] = tmp[i];
        }
        res = s[28];
        if(tag == 0) tag = target;
        else tag = g[tag][target];
    }
}t[N<<2];
/*
    下面初始res取 s[28]的原因是32个数字中第28个是 1
*/
void build(int p, int l, int r){
    t[p].l = l;t[p].r = r;
    if(l == r){
        for(int i=1;i<=32;i++){
            t[p].s[i] = a[l][i] % 2019;
        }
        t[p].res = t[p].s[28];
        t[p].tag = 0;
        return;
    }
    int mid = l + r >> 1;
    build(p*2, l, mid);
    build(p*2+1, mid+1, r);
    for(int i=1;i<=32;i++){
        t[p].s[i] = t[p*2].s[i] + t[p*2+1].s[i];
    }
    t[p].res = t[p].s[28];
    t[p].tag = 0;
}
void pushdown(int p){
    if(t[p].tag){
        t[2*p].convert(t[p].tag);
        t[2*p+1].convert(t[p].tag);
        t[p].tag = 0;
    }
}
int ask(int p, int l, int r){
    if(t[p].l >= l && t[p].r <= r){
        return t[p].res;
    }
    pushdown(p);
    int mid = t[p].l + t[p].r >> 1;
    int res = 0;
    if(mid >= l) res = ask(p*2, l, r);
    if(mid < r) res = res + ask(p*2+1, l, r);
    return res;
}
void change(int p, int l, int r, int k){
    if(t[p].l >= l && t[p].r <= r){
        t[p].convert(k+1);
        return;
    }
    pushdown(p);
    int mid = t[p].l + t[p].r >> 1;
    if(mid >= l) change(p*2, l, r, k);
    if(mid < r) change(p*2+1, l, r, k);
    for(int i=1;i<=32;i++) t[p].s[i] = t[p*2].s[i] + t[p*2+1].s[i];
    t[p].res = t[p].s[28];
}
int main(){
    getConvert();
    scanf("%d%d", &n, &q);
    // 由于序列是1...n，所以可以直接用加法递推
    for(int i=1;i<=n;i++){
        for(int j=1;j<=32;j++){
            if(i == 1) a[i][j] = f[j] % mod;
            else a[i][j] = (f[j] + a[i-1][j]) % mod;
        }
    }
    build(1, 1, n);
    while(q--){
        int l, r;
        scanf("%d%d", &l, &r);
        int res = ask(1, l, r);
        printf("%d
", res);
        change(1, l, r, res % 5);
    }
    return 0;
}

最后膜一下500分的那位大佬，在没有oj的情况下可以一发AC实在是非人哉

感谢耐心指导我的cls（杭电WF选手）

附样例2输入数据