希望能补完。

拖了好几天终于补完了。

[1001 I love cube]

solution

题面：问三维格点正方体内有多少个每条边平行三条坐标轴的等边三角形。

做法：凭借高中立体几何知识，我们知道正方体取三个相邻平面的对角线是可以构造等边三角形的。一方面，我们容易证明一个平面上是不存在格点三角形的，这可以利用设两个点为 以求出第三个点发现。另一方面，当我们确定了一条边时，容易发现存在另一条边与它长度相等且夹角为 的当且仅当确定的那条边是一个正方形的对角线。而一个正方体这样的等边三角形是 个。于是这题就等价于寻找正方体个数了。我们枚举正方体边长 ，每个坐标轴都可以移动 ，于是总的个数就是 了。时间复杂度 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//2021.7.23 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    inline void MAIN(){
        res T=read();
        while(T--){
            RG LL n=Read();
            res m=int(n%kcz);
            printf("%d\n",mul(mul(mul(m-1,m-1),mul(m,m)),2));
        }
    }
}

[1002 I love tree]

solution

题面：给出一棵树，每次修改一条路径 ​，假设点 ​ 是这条路径上的第 ​​ 个点，那它点权增加 ​，询问一个点的点权。

做法：考虑利用深度维护点权变化，若一个点是另一个点的祖先，那么它的点权改变就是 ​​，拆掉后，发现只用维护它被修改的次数、、。若不是祖先，就先找到两者的 lca，分两段维护。发现这些操作都可以轻重链剖分+线段树解决，时间复杂度 。

所以为什么不是询问子树啊。

似乎还有对时间分块的做法，这里就不提了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
//2021.7.22 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=5e5+10;
namespace MAIN{
    int n;
    vector<int> G[N];
    int dep[N],fa[N],sz[N],son[N];
    int F[N][21];
    void dfs_son(res x,res fax,res depx){
        dep[x]=depx,fa[x]=fax,sz[x]=1;
        F[x][0]=fax;
        for(res i=1;i<=20;i++)F[x][i]=F[F[x][i-1]][i-1];
        for(auto tox:G[x]){
            if(tox==fax)continue;
            dfs_son(tox,x,depx+1),sz[x]+=sz[tox];
            if(sz[tox]>sz[son[x]])son[x]=tox;
        }
    }
    int top[N],dfn[N],low[N],idx;
    void dfs_chain(res x,res topx){
        top[x]=topx,dfn[x]=++idx;
        if(son[x])dfs_chain(son[x],topx);
        for(auto tox:G[x]){
            if(tox==fa[x]||tox==son[x])continue;
            dfs_chain(tox,tox);
        }
        low[x]=idx;
    }
    struct P{
        LL sqr,sum;
        int num;
        P() {}
        P(RG LL sqr,RG LL sum,res num):sqr(sqr),sum(sum),num(num) {}
        inline P operator + (const RG P &B) const {
            return P(sqr+B.sqr,sum+B.sum,num+B.num);
        }
        inline void init(){
            sqr=sum=num=0;
        }
    }laz[N<<2];
    //laz0 \sum t^2 laz1 \sum t
    inline void change(const res &rt,const RG P &val){
        laz[rt]=laz[rt]+val;
    }
    inline void pushdown(const res &rt){
        change(rt<<1,laz[rt]),change(rt<<1|1,laz[rt]),laz[rt].init();
    }
    void modify(res rt,res l,res r,const res &L,const res &R,const RG LL &val){
        if(L<=l&&r<=R){change(rt,P(val*val,val,1));return;}
        pushdown(rt);
        res mid=(l+r)>>1;
        if(L<=mid)modify(rt<<1,l,mid,L,R,val);
        if(R>mid)modify(rt<<1|1,mid+1,r,L,R,val);
    }
    LL query(res rt,res l,res r,const res &p,const res &I){
        if(l==r){
            return 1ll*dep[I]*dep[I]*laz[rt].num+laz[rt].sqr-2ll*laz[rt].sum*dep[I];
        }
        pushdown(rt);
        res mid=(l+r)>>1;
        if(p<=mid)return query(rt<<1,l,mid,p,I);
        return query(rt<<1|1,mid+1,r,p,I);
    }
    inline void modify_chain(res x,res y,res va){
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]])swap(x,y);
            modify(1,1,n,dfn[top[x]],dfn[x],va),x=fa[top[x]];
        }
        if(dep[x]<dep[y])swap(x,y);
        modify(1,1,n,dfn[y],dfn[x],va);
    }
    inline int get_lca(res x,res y){
        for(;top[x]!=top[y];dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]]);
        return dep[x]<dep[y]?x:y;
    }
    inline int get_son(res x,res y){
        res pos=dep[x]-dep[y]-1;
        for(res i=20;~i;i--)if(pos&(1<<i))x=F[x][i];
        return x;
    }
    inline void MAIN(){
        n=read();
        for(res i=1;i<n;i++){
            res u=read(),v=read();
            G[u].pb(v),G[v].pb(u);
        }
        dfs_son(1,0,1),dfs_chain(1,1);
        res q=read();
        while(q--){
            res opt=read();
            if(opt==1){
                res x=read(),y=read();
                res LCA=get_lca(x,y);
                if(x!=LCA&&y!=LCA){
                    modify_chain(x,LCA,dep[x]+1);
                    res s=get_son(y,LCA);
                    modify_chain(y,s,-(dep[x]-dep[LCA]+1-dep[LCA]));
                }
                else if(x==LCA){
                    modify_chain(x,y,dep[x]-1);
                }
                else {
                    modify_chain(x,y,dep[x]+1);
                }
            }
            else {
                res x=read();
                printf("%lld\n",query(1,1,n,dfn[x],x));
            }
        }
    }
}

[1003 I love playing games]

solution

题面：A 和 B 在一张无向图上博弈，每一回合两人分别可以沿一条边走过去。一个点可以同时容纳两个人当且仅当这个点是起点或终点（二者起点可以不同，终点一定相同），先到终点的人获胜。问结果是平局（平局当且仅当一回合内两人都走到终点）还是谁赢？

做法：显然，若一个人到终点的最短路长小于另外一个，则这个人必胜。

那么剩下来就是最短路长相等的情况了，题解的做法是直接暴力求 sg 函数，即设 ​ 表示当前 A 在 ​​​ 点 B 在 ​ 点当前轮到谁走的胜负情况。转移就是按着分层图转移就行了，复杂度 ​。

实际上，我们改变一下 sg 的设法，换成 表示一个点集 记录 B 在 ​​​ 点 A 在 ​ 点时 A 必胜。

这样的好处是什么呢？我们发现这样转移可以 bitset 压位，使总时间复杂度变成 ，跑得更快了！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//2021.7.25 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e3+10;
namespace MAIN{
    int n,m,x,y,z;
    vector<int> G[N];
    bitset<N> f[N],ret;
    int dep[N];
    int Q[N],he,ta;
    inline void MAIN(){
        res T=read();
        while(T--){
            n=read(),m=read(),x=read(),y=read(),z=read();
            for(res i=1;i<=n;i++)vector<int>().swap(G[i]),dep[i]=inf;
            for(res i=1;i<=m;i++){
                res u=read(),v=read();
                G[u].pb(v),G[v].pb(u);
            }
            dep[Q[he=ta=1]=z]=0;
            while(he<=ta){
                res u=Q[he++];
                for(auto tox:G[u])if(dep[tox]==inf)dep[tox]=dep[u]+1,Q[++ta]=tox;
            }
            dep[Q[ta+1]=0]=inf;
            if(dep[x]<dep[y])puts("1");
            else if(dep[x]>dep[y])puts("3");
            else {
                if(dep[x]==inf&&dep[y]==inf){puts("2");continue;}
                if(x==z&&y==z){puts("2");continue;}
                if(dep[x]==1&&dep[y]==1){puts("2");continue;}
                for(res i=1;i<=n;i++)f[i].reset();
                for(res d=1,i=2;d<=dep[x];d++){
                    while(dep[Q[i]]==d){
                        if(d!=1){
                            ret.set();
                            for(auto tox:G[Q[i]])if(dep[tox]+1==dep[Q[i]])ret&=f[tox];
                            for(auto u=ret._Find_first();u!=N;u=ret._Find_next(u))
                                for(auto tox:G[u])if(dep[tox]==dep[Q[i]])f[Q[i]].set(tox);
                        }
                        f[Q[i]].set(Q[i]),i++;
                    }
                }
                puts(f[y][x]?"1":"2");
            }
        }
    }
}

[1004 I love counting]

solution

题面：给你 个数 ，每次询问 ，问 区间里有多少个不同的 满足 。

做法：受上一场多校的影响，我上来就胡了莫队 +Trie 的做法，没想到 ​​ 一下子就跑过了 ​​​ 啊，感谢出题人的不杀之恩。

正解是 ​​ 的 Trie，想想也确实不难。区间不同颜色可以用 ​​ 和 ​​ 满足来说明，而 ​ 可以直接在 Trie 树上预处理好，于是总复杂度就是 ​ 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//2021.7.24 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int tr[N*20][2],tot,rt,ans[N],n;
    struct P{
        int l,r,id,op;
        P() {}
        P(res l,res r,res id,res op):l(l),r(r),id(id),op(op) {}
        inline bool operator < (const RG P &B) const {
            return l!=B.l?l<B.l:op>B.op;
        }
    };
    vector<P> que[N*20];
    int pre[N],pos[N];
    inline void insert(const res &x,const res &I){
        if(!rt)rt=++tot;
        RG P ret=P(pre[I]+1,I+1,0,0);
        res now=rt;
        for(res i=20;~i;i--){
            res d=(x>>i)&1,&to=tr[now][d];
            if(!to)to=++tot;
            now=to,que[now].pb(ret);
        }
    }
    inline void insert(const res &l,const res &r,const res &a,const res &b,const res &I){
        if(!rt)rt=++tot;
        RG P ret=P(l+1,r+1,I,1);
        res now=rt;
        for(res i=20;~i;i--){
            res d=(a>>i)&1,c=(b>>i)&1;
            res to=tr[now][d];
            if(to&&c)que[to].pb(ret);
            if(c)now=tr[now][d^1];
            else now=tr[now][d];
        }
        if(now)que[now].pb(ret);
    }
    int t[N];
    inline void modify(const res &x,const res &y){
        for(res i=x;i<=n+1;i+=lowbit(i))t[i]+=y;
    }
    inline int query(const res &x){
        res ret=0;
        for(res i=x;i;i-=lowbit(i))ret+=t[i];
        return ret;
    }
    inline void MAIN(){
        n=read();
        for(res i=1;i<=n;i++){
            res x=read();
            pre[i]=pos[x],pos[x]=i,insert(x,i);
        }
        res q=read();
        for(res i=1;i<=q;i++){
            res l=read(),r=read(),a=read(),b=read();
            insert(l,r,a,b,i);
        }
        for(res i=2;i<=tot;i++){
            sort(que[i].begin(),que[i].end());
            for(auto x:que[i])if(!x.op)modify(x.r,1);else ans[x.id]+=query(x.r)-query(x.l-1);
            for(auto x:que[i])if(!x.op)modify(x.r,-1);
        }
        for(res i=1;i<=q;i++)printf("%d\n",ans[i]);
    }
}

[1005 I love string]

solution

题面：每次丢进一个字符，可以放在最前面和最后面，希望最终字符串字典序最小，问方案数。

做法：贪心地想，更小的字符肯定扔到前面，更大的字符肯定扔到后面，只有头尾和当前都相同的字符才有不同方案，模拟即可。时间复杂度 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//2021.7.22 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    char str[N];
    inline void MAIN(){
        res T=read();
        while(T--){
            res n=read(),ans=1;
            scanf("%s",str+1);
            RG char head=str[1],tail=str[1];
            for(res i=2;i<=n;i++){
                if(str[i]<head)head=str[i];
                else if(str[i]>tail)tail=str[i];
                else if(str[i]==head&&str[i]==tail)ans=mul(ans,2);
            }
            printf("%d\n",ans);
        }
    }
}

[1006 I love sequences]

solution

题面：给出 ​ ，求 ，其中 ，定义 。​​​

做法：​ 的求法就很像 FWT 那种卷积，我们试着按照 FWT 的方式求一下。

容易写出 的 的情况：

​

按照 FWT 的逻辑，我们需要凑出右边都是形式相同的乘积，发现很容易凑出。

于是就可以用 FWT 求出 ​ 了。

我们考虑一下复杂度，每次卷积长度为 ，那么求 的复杂度就是 ，再暴力一项项与 ​​ 相乘，总复杂度还是 ​。

于是最终复杂度就是 ​。而这个复杂度是容易积分分析的，是 。

实现时能用之前的 就用之前的 ，不然的话可能会跑不过去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//2021.7.25 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=6e5+10;
namespace MAIN{
    int a[N],b[N],c[N],pw[N];
    inline void FWT(res *A,const res &lim){
        for(res i=0;i<lim;i++)
            for(res j=0;j<pw[lim];j+=pw[i+1])
                for(res k=0;k<pw[i];k++)
                    add(A[j+k+2*pw[i]],A[j+k]),add(A[j+k+pw[i]],A[j+k+2*pw[i]]);
    }
    inline void IFWT(res *A,const res &lim){
        for(res i=0;i<lim;i++)
            for(res j=0;j<pw[lim];j+=pw[i+1])
                for(res k=0;k<pw[i];k++)
                    add(A[j+k+pw[i]],kcz-A[j+k+2*pw[i]]),add(A[j+k+2*pw[i]],kcz-A[j+k]);
    }
    int d[N];
    int A[N],B[N];
    inline int solve(const res &n){
        res l=0;
        for(;pw[l]<=n;l++);
        for(res i=0;i<pw[l];i++)A[i]=B[i]=0;
        for(res i=1;i<=n;i++)A[i]=a[i],B[i]=b[i];
        FWT(A,l),FWT(B,l);
        for(res i=0;i<pw[l];i++)d[i]=mul(A[i],B[i]);
        IFWT(d,l);
        return l;
    }
    inline void MAIN(){
        res n=read();
        pw[0]=1;
        for(res i=1;;i++){
            pw[i]=pw[i-1]*3;
            if(pw[i]>=3*n)break;
        }
        for(res i=1;i<=n;i++)a[i]=read();
        for(res i=1;i<=n;i++)b[i]=read();
        for(res i=1;i<=n;i++)c[i]=read();
        res ans=0,t=0;
        for(res i=1;i<=n;i++){
            if(i==1)t=solve(n/i);
            else if((n/i)!=(n/(i-1)))t=solve(n/i);
            for(res j=1,ret=c[i];j<pw[t];j++,ret=mul(ret,c[i]))add(ans,mul(ret,d[j]));
        }
        printf("%d\n",ans);
    }
}

[1007 I love data structure]

solution

题面：各有 ​ 个数 ，现有四种操作

  1. 区间加（ 或 ​）。
  2. 区间 和 ​ 交换。
  3. 区间 。
  4. 区间求和 。

做法：难点就在第三个操作，直接打几次操作三的标记的话你会发现复杂度不能接受。实际上你可以让 ​​ 表示成矩阵 ​​​，​而操作三就是 ​​，那么操作三​就可以叠加了。于是总复杂度就变成了 ，只不过常数要乘 。

实现上，其他操作都可以写成矩阵，不过矩阵会变大，常数就会变大，这里看各位的实现吧。

其实挺难写的，因为为了维护 ​，你还要维护 ，然后tag 传下去的时候还要修改这些东西，这些都要手玩，而且还很复杂（这里是建立在不给这些都建矩阵，如果都建的话矩阵要 了）。​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
//2021.7.24 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN{
    struct P{
        int sum,sqr,laz;
        inline void upd(const res &x){
            add(sum,x),add(sqr,mul(x,x));
        }
    }tra[N<<2],trb[N<<2];
    int ans[N<<2],rev[N<<2],len[N<<2];
    struct Matrix{
        int t[2][2];
        inline void init(){
            t[0][0]=t[1][0]=t[0][1]=t[1][1]=0;
        }
        inline void ini(){
            t[0][0]=t[0][1]=3,t[1][0]=2,t[1][1]=kcz-2;
        }
        inline void in(){
            t[0][0]=t[1][1]=1,t[0][1]=t[1][0]=0;
        }
        inline void sw(){
            res a=t[0][0],b=t[0][1],c=t[1][0],d=t[1][1];
            t[0][0]=b,t[0][1]=a,t[1][1]=c,t[1][0]=d;
        }
        inline void rev(){
            t[0][0]=t[1][1]=0,t[0][1]=t[1][0]=1;
        }
    }tag[N<<2],o,p,q;
    inline Matrix operator * (const RG Matrix &A,const RG Matrix &B){
        Matrix c;
        c.init();
        for(res i=0;i<2;i++)for(res j=0;j<2;j++){
            RG LL ret=0;
            for(res k=0;k<2;k++)ret+=1ll*A.t[i][k]*B.t[k][j];
            c.t[i][j]=int(ret%kcz);
        }
        return c;
    }
    inline void pushup(const res &rt){
        tra[rt].sum=Add(tra[rt<<1].sum,tra[rt<<1|1].sum);
        tra[rt].sqr=Add(tra[rt<<1].sqr,tra[rt<<1|1].sqr);
        trb[rt].sum=Add(trb[rt<<1].sum,trb[rt<<1|1].sum);
        trb[rt].sqr=Add(trb[rt<<1].sqr,trb[rt<<1|1].sqr);
        ans[rt]=Add(ans[rt<<1],ans[rt<<1|1]);
    }
    void build(res rt,res l,res r){
        len[rt]=r-l+1,tag[rt].in();
        if(l==r){
            res a=int(Read()%kcz),b=int(Read()%kcz);
            tra[rt].upd(a),trb[rt].upd(b);
            ans[rt]=mul(a,b);
            return;
        }
        res mid=(l+r)>>1;
        build(rt<<1,l,mid),build(rt<<1|1,mid+1,r),pushup(rt);
    }
    inline void change(const res &rt,const res &va,const res &vb,const res &re,const RG Matrix &tg){
//        if(re)swap(tra[rt],trb[rt]),tag[rt].sw();
        res sqra=tra[rt].sqr,sqrb=trb[rt].sqr,sa=tra[rt].sum,sb=trb[rt].sum,as=ans[rt];
        res la=tra[rt].laz,lb=trb[rt].laz,c=tg.t[0][0],d=tg.t[0][1],e=tg.t[1][0],f=tg.t[1][1];
        ans[rt]=Add(Add(mul(sqra,mul(c,d)),mul(sqrb,mul(e,f))),mul(as,Add(mul(c,f),mul(d,e))));
        tra[rt].sqr=Add(Add(mul(sqr(c),sqra),mul(sqr(e),sqrb)),dou(mul(as,mul(c,e))));
        trb[rt].sqr=Add(Add(mul(sqr(d),sqra),mul(sqr(f),sqrb)),dou(mul(as,mul(d,f))));
        tra[rt].sum=Add(mul(sa,c),mul(sb,e));
        trb[rt].sum=Add(mul(sa,d),mul(sb,f));
        tra[rt].laz=Add(mul(la,c),mul(lb,e));
        trb[rt].laz=Add(mul(la,d),mul(lb,f));
        tag[rt]=tag[rt]*tg;
//        ans[rt]=Add(mul(9,sqra),kcz-mul(4,sqrb));
//        tra[rt].sum=Add(mul(3,sa),Add(sb,sb));
//        trb[rt].sum=Add(mul(3,sa),kcz-Add(sb,sb));
//        tra[rt].sqr=Add(Add(mul(9,sqra),mul(4,sqrb)),mul(12,as));
//        tra[rt].sqr=Add(Add(mul(9,sqra),mul(4,sqrb)),kcz-mul(12,as));
        add(ans[rt],Add(mul(len[rt],mul(va,vb)),Add(mul(trb[rt].sum,va),mul(tra[rt].sum,vb))));
        add(tra[rt].sqr,Add(mul(sqr(va),len[rt]),mul(dou(va),tra[rt].sum)));
        add(trb[rt].sqr,Add(mul(sqr(vb),len[rt]),mul(dou(vb),trb[rt].sum)));
        add(tra[rt].sum,mul(va,len[rt])),add(trb[rt].sum,mul(vb,len[rt]));
        add(tra[rt].laz,va),add(trb[rt].laz,vb);
        rev[rt]^=re;
    }
    inline void pushdown(const res &rt){
        change(rt<<1,tra[rt].laz,trb[rt].laz,rev[rt],tag[rt]),change(rt<<1|1,tra[rt].laz,trb[rt].laz,rev[rt],tag[rt]);
        tra[rt].laz=trb[rt].laz=rev[rt]=0,tag[rt].in();
    }
    void modify0(res rt,res l,res r,const res &L,const res &R,const res &v,const res &op){
        if(L<=l&&r<=R){
            if(op==0)change(rt,v,0,0,o);
            else change(rt,0,v,0,o);
            return;
        }
        pushdown(rt);
        res mid=(l+r)>>1;
        if(L<=mid)modify0(rt<<1,l,mid,L,R,v,op);
        if(R>mid)modify0(rt<<1|1,mid+1,r,L,R,v,op);
        pushup(rt);
    }
    void modify1(res rt,res l,res r,const res &L,const res &R){
        if(L<=l&&r<=R){
            change(rt,0,0,0,p);
            return;
        }
        pushdown(rt);
        res mid=(l+r)>>1;
        if(L<=mid)modify1(rt<<1,l,mid,L,R);
        if(R>mid)modify1(rt<<1|1,mid+1,r,L,R);
        pushup(rt);
    }
    void modify2(res rt,res l,res r,const res &L,const res &R){
        if(L<=l&&r<=R){
            change(rt,0,0,1,q);
            return;
        }
        pushdown(rt);
        res mid=(l+r)>>1;
        if(L<=mid)modify2(rt<<1,l,mid,L,R);
        if(R>mid)modify2(rt<<1|1,mid+1,r,L,R);
        pushup(rt);
    }
    int query(res rt,res l,res r,const res &L,const res &R){
        if(L<=l&&r<=R)return ans[rt];
        pushdown(rt);
        res mid=(l+r)>>1,ret=0;
        if(L<=mid)ret=query(rt<<1,l,mid,L,R);
        if(R>mid)add(ret,query(rt<<1|1,mid+1,r,L,R));
        pushup(rt);
        return ret;
    }
    inline void MAIN(){
        o.in(),p.ini(),q.rev();
        res n=read();
        build(1,1,n);
        res q=read();
        while(q--){
            res opt=read();
            if(opt==1){
                res tag=read(),l=read(),r=read(),x=int(Read()%kcz);
                modify0(1,1,n,l,r,x,tag);
            }
            if(opt==2){
                res l=read(),r=read();
                modify1(1,1,n,l,r);
            }
            if(opt==3){
                res l=read(),r=read();
                modify2(1,1,n,l,r);
            }
            if(opt==4){
                res l=read(),r=read();
                printf("%d\n",query(1,1,n,l,r));
            }
        }
    }
}

[1008 I love exam]

solution

题面：有 ​ 个三元组 ，表示为要学习 天 号考试加 ​ 分（单门课程不能超过 ​​）。小于 算挂科，最多只能挂 门课。在不挂 ​ 门以上的情况中，最多能得多少总分？

做法：考虑对每号考试做一个背包，即 表示 ​ 号考试共花 天的最大分数。然后再合并这些背包，即设 表示刚才算到第 号考试用了 天挂了 门的最大分数，直接暴力做就是 的了。

注意一下最大分数不能超过 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//2021.7.24 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    map<string,int> M;
    int f[50+10][500+10];
    int g[500+10][5][50+10];
    inline void MAIN(){
        res T=read();
        while(T--){
            res n=read();
            map<string,int>().swap(M);
            for(res i=1;i<=n;i++){
                RG string s;
                cin>>s,M[s]=i;
            }
            res m=read();
            for(res d=1;d<=n;d++)for(res j=0;j<=500;j++){
                f[d][j]=0;
                for(res i=0;i<=4;i++)g[j][i][d]=0;
            }
            for(res i=1;i<=m;i++){
                string s;
                cin>>s;
                res x=read(),y=read(),d=M[s];
                for(res j=500;j>=y;j--)if(f[d][j-y]||j==y)f[d][j]=min(max(f[d][j],f[d][j-y]+x),100);
            }
            res t=read(),p=read();
            for(res i=0;i<=t;i++){
                for(res j=1;j<=n;j++){
                    for(res k=0;k<=p;k++){
                        if(g[i][k][j-1]||(i==0&&j==1&&k==0)){
                            for(res l=1;i+l<=t;l++){
                                if(f[j][l]>=60){
                                    g[i+l][k][j]=max(g[i][k][j-1]+f[j][l],g[i+l][k][j]);
                                }
                                else g[i+l][k+1][j]=max(g[i][k][j-1]+f[j][l],g[i+l][k+1][j]);
                            }
                        }
                    }
                }
            }
            res ans=0;
            for(res i=1;i<=t;i++)for(res j=0;j<=p;j++)ans=max(ans,g[i][j][n]);
            printf("%d\n",ans==0?-1:ans);
        }
    }
}

[1009 I love triples]

solution

题面：给你 个数，问有多少个无序三元组 ​​，满足 为完全平方数？

做法：我们考虑存在一个无序三元组 满足 。为什么要想到这样的三元组呢？这是因为枚举这样的三元组的时间复杂度会是 ​ 的​​​。我们分析一下复杂度，写出来的伪代码应该是这样的:

1
2
3
For x=1 to n
	For y=1 to min(x,n/x)
		For z=1 to y

而这段代码的复杂度应该是

于是枚举三元组的复杂度我们可以接受了，但很可惜的是， 未必能构造出所有的 ​。

不过，我们惊喜地发现，若 ​ 中没有完全平方数，则一定有一组 能构造出它。接下来我们来证明这件事。

我们现在考虑设 为 去掉所有平方质因子的数。对于 ​ ，我们让其变成 ​​​。若我们能构造一组 能满足 ，就也就能构造一组满足 。为了方便书写，我们把 ​ 写成 。

若 中无完全平方数，那么 一定能写成 ，其中 是奇质数。因为 是完全平方数，所以 一定也有 这个因子。那我们不妨设 ，而 ，那么完全平方数的限制就要求 ，于是就证明出来了。

因此，我们在用埃氏筛求出 后，对完全平方数作特殊讨论。有完全平方数时，另两个要么都是完全平方数，要么乘起来是完全平方数但单独不是。其余的非完全平方数我们就在 的时间复杂度里枚举 来求出， 是不同的 的个数。

实际上，​​​​ 同阶，不过 ​​ 在 ​​​ 时只有 ​​ 左右，所以跑得飞快。

总时间复杂度 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//2021.7.23 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int n;
    int t[N],cnt[N];
    inline void MAIN(){
        t[1]=1;
        for(res i=2;i<=N-10;i++){
            if(!t[i]){
                t[i]=i;
                for(res j=2;j*i<=N-10;j++)t[i*j]=(t[j]%i)?t[j]*i:t[j]/i;
            }
        }
        res T=read();
        while(T--){
            n=read();
            for(res i=1;i<=N-10;i++)cnt[i]=0;
            for(res i=1;i<=n;i++)cnt[t[read()]]++;
            RG LL ans=1ll*cnt[1]*(cnt[1]-1)*(cnt[1]-2)/6;
            for(res i=2;i<=N-10;i++)ans+=1ll*cnt[1]*cnt[i]*(cnt[i]-1)/2;
            for(res x=1;x<=N-10;x++)if(t[x]==x)for(res y=1;x*y<=N-10&&y<x;y++)if(t[y]==y)for(res z=1;z<y;z++)if(t[z]==z)ans+=1ll*cnt[x*y]*cnt[x*z]*cnt[y*z];
            printf("%lld\n",ans);
        }
    }
}

[1010 I love permutation]

solution

题面：给出 ​，​ 是奇质数，​，求 ​ 数组逆序对的奇偶。

做法：打表就发现奇偶就是 是否是模 的二次剩余了，所以套个板子就好了。

证明也很简单，因为 是奇质数，那么 ​ 数组是 ​ 的排列。于是

于是就与猜的二次剩余结论一致了。时间复杂度 ​。​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//2021.7.23 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    inline LL mult(const RG LL &x,const RG LL &y,const RG LL &p){
        return (x*y-(LL)((long double)x/p*y)*p+p)%p;
    }
    inline void MAIN(){
        res T=read();
        while(T--){
            RG LL a=Read(),P=Read();
            RG LL m=(P-1)/2;
            RG LL ret=1;
            while(m){
                if(m&1)ret=mult(ret,a,P);
                a=mult(a,a,P),m>>=1;
            }
            if(ret==1)puts("0");
            else puts("1");
        }
    }
}

[1011 I love max and multiply]

solution

题面：给 ​​，​​，求 ​​。​

做法：题是简单题，但我忘记了 可以为负数，然后 add 的时候一直在出错。。。调了一小时，心态崩了。

我们直接对每个 求 和 ，然后做一个后缀取 ，就做完了。

时间复杂度 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//2021.7.23 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=(1<<18)+10;
namespace MAIN{
    int n;
    int mxa[N],mxb[N],mna[N],mnb[N];
    LL c[N];
    inline void MAIN(){
        res T=read();
        while(T--){
            res n=read(),ans=0;
            for(res i=0;i<n;i++)mxa[i]=mna[i]=read();
            for(res i=0;i<n;i++)mxb[i]=mnb[i]=read();
            c[n]=-0x8000000000000000ll;
            for(res S=n-1;~S;S--){
                for(res i=0;i<=18;i++)
                    if((S|(1<<i))<n)
                        mxa[S]=max(mxa[S],mxa[S|(1<<i)]),mxb[S]=max(mxb[S],mxb[S|(1<<i)]),
                        mna[S]=min(mna[S],mna[S|(1<<i)]),mnb[S]=min(mnb[S],mnb[S|(1<<i)]);
                c[S]=max({c[S+1],1ll*mxa[S]*mxb[S],1ll*mna[S]*mnb[S],1ll*mna[S]*mxb[S],1ll*mxa[S]*mnb[S]});
                add(ans,Add(int(c[S]%kcz),kcz));
            }
            printf("%d\n",ans);
        }
    }
}

[1012 I love 114514]

solution

题面：问你一个串里有没有 。

做法：好臭的签到题，这样臭的题有存在的必要吗（bushi

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//2021.7.22 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    char str[N];
    inline void MAIN(){
        res T=read();
        while(T--){
            scanf("%s",str+1);
            res n=int(strlen(str+1));
            RG bool fl=0;
            for(res i=1;i<=n-5;i++){
                if(str[i]=='1'&&str[i+1]=='1'&&str[i+2]=='4'&&str[i+3]=='5'&&str[i+4]=='1'&&str[i+5]=='4'){
                    fl=1;break;
                }
            }
            if(fl)puts("AAAAAA");
            else puts("Abuchulaile");
        }
    }
}