注意到我们可以用矩阵乘法做

\[
\begin{bmatrix}
a & 1 \\
\end{bmatrix}
\begin{pmatrix}
1 \\
b \\
\end{pmatrix}
\text{=}
\begin{bmatrix}
a+b \\
\end{bmatrix}
\]

#include<bits/stdc++.h>
#define LL long long
#define sz 5
#define MOD 998244353
using namespace std;

struct mat {
    LL a[sz][sz];
    
    mat() { memset(a, 0, sizeof a); }
    
    mat operator-(const mat& T) const {
        mat res;
        for (int i = 0; i < sz; ++i)
            for (int j = 0; j < sz; ++j) {
                res.a[i][j] = (a[i][j] - T.a[i][j]) % MOD;
            }
        return res;
    }
    
    mat operator+(const mat& T) const {
        mat res;
        for (int i = 0; i < sz; ++i)
            for (int j = 0; j < sz; ++j) {
                res.a[i][j] = (a[i][j] + T.a[i][j]) % MOD;
            }
        return res;
    }
    
    mat operator*(const mat& T) const {
        mat res;
        int r;
        for (int i = 0; i < sz; ++i)
            for (int k = 0; k < sz; ++k) {
                r = a[i][k];
                for (int j = 0; j < sz; ++j)
                    res.a[i][j] += T.a[k][j] * r, res.a[i][j] %= MOD;
            }
        return res;
    }
    
    mat operator^(LL x) const {
        mat res, bas;
        for (int i = 0; i < sz; ++i) res.a[i][i] = 1;
        for (int i = 0; i < sz; ++i)
            for (int j = 0; j < sz; ++j) bas.a[i][j] = a[i][j] % MOD;
        while (x) {
            if (x & 1) res = res * bas;
            bas = bas * bas;
            x >>= 1;
        }
        return res;
    }
};


int main(){
    int a, b;
    cin>>a>>b;
    mat mata, matb;
    mata.a[0][0] = a;
    mata.a[0][1] = 1;
    matb.a[0][0] = 1;
    matb.a[1][0] = b;
    mat matc = mata*matb;
    cout<<matc.a[0][0]<<endl;
    
    return 0;
}

注意到数据范围为\(2^{15}-1\)，故可以用树状数组做。

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

int c[40000];

int lowbit(int x){return x&(-x);}
void update(int i){
    while(i<=40000){
        c[i]++;
        i+=lowbit(i);
    }
}
int getsum(int i){
    int res=0;
    while(i>0){res+=c[i];i-=lowbit(i);}
    return res;
}

int main(){
    int x,y;
    cin>>x>>y;
    for(int i=1;i<=x;i++)update(i);
    for(int i=1;i<=y;i++)update(i);
    cout<<getsum(max(x,y));
    return 0;
}

很显然，这是一道 dijkstra 的模板题（

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int MAXM = 2e5 + 10;
const int MAXN = 1e5 + 10;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, dis, next;
};

int cnt, head[MAXN], dis[MAXM];
bool vis[MAXN];

Edge e[MAXM];

inline void add(int u, int v, int w) {
    e[++cnt].dis = w;
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}

struct node {
    int dis, pos;
    bool operator < (const node &x) const {
        return x.dis < dis;
    }
};

priority_queue<node> q;

void dijkstra(int s) {
    memset(dis, INF, sizeof(dis));
    dis[s] = 0;
    q.push({dis[s], s});
    while (!q.empty()) {
        int u = q.top().pos;
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].to;
            if (dis[v] > dis[u] + e[i].dis) {
                dis[v] = dis[u] + e[i].dis;
                if (!vis[v]) q.push({dis[v], v});
            }
        }
    }
}

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    add(1, 2, a);
    add(2, 3, b);
    dijkstra(1);
    printf("%d\n", dis[3]);
    return 0;
}

这道题难度介于紫和黑之间，但只要想到a+b和多项式乘法之间的关系，那么就可以套模板了

注意到 \((x+a)(x+b)=x^2+(a+b)x+ab\)，所以要求 \(a+b\)，只需求 \((x+a)(x+b)\) 即可。

这是一个多项式乘法问题，我们可以用NTT做。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=167772161;
inline int qpow(int x,int k){
    int res=1;
    while(k){
        if(k&1) res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return res;
}


template<int MAXN>
struct Poly{
    int length;
    int a[MAXN];
    int bit,len,g=3,rev[MAXN];
    void NTT(int*a,int opt){
        for(int i=0;i<len;i++)
            if(i<rev[i]) swap(a[i],a[rev[i]]);
        for(int mid=1;mid<len;mid<<=1){
            int tmp;
            if(opt==1) tmp=qpow(g,(mod-1)/(mid<<1));
            else tmp=qpow(55924054,(mod-1)/(mid<<1));
            for(int i=0,mid2=(mid<<1);i<len;i+=mid2){
                int w=1;int t=mid+i;
                for(int j=i;j<t;j++,w=1ll*w*tmp%mod){
                    int y=1ll*w*a[j+mid]%mod;
                    a[j+mid]=(a[j]-y+mod)%mod;a[j]=(a[j]+y)%mod;
                }
            }
        }
    }
    void Multiply(Poly& pol){
        int n,m;
        n=length;m=pol.length;
        len=1;bit=0;
        while(len<=n+m)len<<=1,bit++;
        for(signed i=0;i<len;i++) rev[i]=(rev[i>>1]>>1) | ((i&1)<<(bit-1));
        NTT(a,1);NTT(pol.a,1);
        for(signed i=0;i<len;i++) a[i]=1ll*a[i]*pol.a[i]%mod;
        NTT(a,-1);
        int inv=qpow(len,mod-2);
        for(signed i=0;i<=n+m;i++){
            a[i]=1ll*a[i]*inv%mod;
        }length=n+m;
        memset(pol.a,0,sizeof pol.a);
    }
};
Poly<5>p1,p2;

signed main(){
    int n,m;cin>>n>>m;
    p1.length=p2.length=1;
    p1.a[0]=n,p2.a[0]=m;
    p1.a[1]=p2.a[1]=1;
    p1.Multiply(p2);
    cout<<p1.a[1];
    return 0;
}

很显然，这是一道分块的模板题

#include<bits/stdc++.h>
#define ll long long
#define run int _T;cin>>_T;while(_T--)
#define IO_Setup(Name) \
    FastIO; \
    freopen((Name ".in"), "r", stdin); \
    freopen((Name ".out"), "w", stdout);
#define FastIO \
    ios::sync_with_stdio(0); \
    cin.tie(0); \
    cout.tie(0);
#define IO_Close \
    fclose(stdin); \
    fclose(stdout);
#ifdef ONLINE_JUDGE
#define DEBUG_FLAG false
#else
#define DEBUG_FLAG true
#endif
#define cdebug if (!DEBUG_FLAG) return
#define MAXN 100005
#define INF 1e9
#define int long long
using namespace std;

int n, k;
int a[MAXN];

int s;
int sum[MAXN], L[MAXN], R[MAXN], belong[MAXN], lazy_tag[MAXN];
/*
sum[i]表示第i块的区间和
L[i]表示第i块的左端点
R[i]表示第i块的右端点
belong[i]表示第i个元素对应的块编号
*/
void build(){
    s = sqrt(n);
    int num = n/s; // 总块数
    if (n % s) num++; // 加角块
    for(int i=1; i<=num; i++){
        L[i] = (i-1)*s+1;
        R[i] = i*s;
    }
    R[num] = n;

    for(int i=1; i<=n; i++){
        belong[i] = (i-1)/s+1;
    }

    for(int i=1; i<=num; i++){
        for(int j=L[i]; j<=R[i]; j++){
            sum[i] += a[j];
        }
    }
}

int query(int l, int r){
    int ans=0;
    if (belong[l] == belong[r]){  // 同一块，暴力求解
        for(int i=l; i<=r; i++){
            ans += a[i] + lazy_tag[belong[l]];
        }
        return ans;
    }
    for(int i=l; i<=R[belong[l]]; i++){ // 处理左边块
        ans += a[i] + lazy_tag[belong[l]];
    }
    for(int i=belong[l]+1; i<belong[r]; i++){ // 处理中间块
        ans += sum[i];
    }
    for(int i=L[belong[r]]; i<=r; i++){ // 处理右边块
        ans += a[i] + lazy_tag[belong[r]];
    }
    return ans;
}

void update(int l, int r, int x){
    if (belong[l] == belong[r]){
        for(int i=l; i<=r; i++){
            a[i] += x;
        }
        sum[belong[l]] += x*(r-l+1);
        return;
    }
    for(int i=l; i<=R[belong[l]]; i++){  // 这是在遍历块内元素
        a[i] += x;
    }
    sum[belong[l]] += x*(R[belong[l]]-l+1);
    for(int i=belong[l]+1; i<belong[r]; i++){  // 这是在遍历整个块
        sum[i] += x*(R[i]-L[i]+1);
        lazy_tag[i] += x;
    }
    for(int i=L[belong[r]]; i<=r; i++){  // 这是在遍历块内元素
        a[i] += x;
    }
    sum[belong[r]] += x*(r-L[belong[r]]+1);
}

signed main(){
    n = 2;
    build();
    cin>>k;
    update(1, 1, k);
    cin>>k;
    update(2, 2, k);
    cout<<query(1, 2)<<endl;
    
    return 0;
}

很显然啊，这是一道 树链剖分 + 线段树 的模版题（

#include <iostream>
using namespace std;

int w[5], wt[5];
int tot = 0, head[5];

struct edge {
    int to, nxt;
} e[10];

void add(int u, int v) {
    e[++tot] = edge{v, head[u]};
    head[u] = tot;
}

int cnt = 0, son[5], siz[5], fa[5], dep[5], id[5], top[5];

void dfs1(int x, int f, int deep) {
    dep[x] = deep;
    fa[x] = f;
    siz[x] = 1;
    int maxson = -1;
    for (int i = head[x]; i; i = e[i].nxt) {
        int y = e[i].to;
        if (y == f) continue;
        dfs1(y, x, deep + 1);
        siz[x] += siz[y];
        if (maxson < siz[y]) {
            maxson = siz[y];
            son[x] = y;
        }
    }
}

void dfs2(int x, int ftop) {
    id[x] = ++cnt;
    wt[cnt] = w[x];
    top[x] = ftop;
    if (!son[x]) return;
    dfs2(son[x], ftop);
    for (int i = head[x]; i; i = e[i].nxt) {
        int y = e[i].to;
        if (y == fa[x] || y == son[x]) continue;
        dfs2(y, y);
    }
}

#define ls(rt) (rt << 1)
#define rs(rt) (rt << 1 | 1)
#define mid ((l + r) >> 1)

int a[20];
//int laz[20];

void push_up(int rt) {
    a[rt] = a[ls(rt)] + a[rs(rt)];
}

//void add_tag(int rt, int l, int r, int k) {
//  laz[rt] += k;
//  a[rt] += (r - l + 1) * k;
//}

//void push_down(int rt, int l, int r) {
//  if (laz[rt]) {
//      add_tag(ls(rt), l, mid, laz[rt]);
//      add_tag(rs(rt), mid + 1, r, laz[rt]);
//      laz[rt] = 0;
//  }
//}

int query(int L, int R, int rt, int l, int r) {
    if (L <= l && R >= r) return a[rt];
    // push_down(rt, l, r);
    int res = 0;
    if (L <= mid) res += query(L, R, ls(rt), l, mid);
    if (R > mid) res += query(L, R, rs(rt), mid + 1, r);
    return res;
}

void build(int rt, int l, int r) {
    if (l == r) {
        a[rt] = wt[l];
        return;
    }
    build(ls(rt), l, mid);
    build(rs(rt), mid + 1, r);
    push_up(rt);
}

//void updRange(int x, int y, int k) {
//  while (top[x] != top[y]) {
//      if (dep[top[x]] < dep[top[y]]) swap(x, y);
//      update(id[top[x]], id[x], 1, 1, 2, k);
//      x = fa[top[x]];
//  }
//  if (dep[x] > dep[y]) swap(x, y);
//  update(id[x], id[y], 1, 1, 2, k);
//}

//int qRange(int x, int y) {
//  int ans = 0;
//  while (top[x] != top[y]) {
//      if (dep[top[x]] < dep[top[y]]) swap(x, y);
//      ans += query(id[top[x]], id[x], 1, 1, 2);
//      x = fa[top[x]];
//  }
//  if (dep[x] > dep[y]) swap(x, y);
//  ans += query(id[x], id[y], 1, 1, 2);
//  return ans;
//}

//void updSon(int x, int k) {
//  update(id[x], id[x] + siz[x] - 1, 1, 1, 2, k);
//}

int qSon(int x) {
    return query(id[x], id[x] + siz[x] - 1, 1, 1, 2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> w[1] >> w[2];
    add(1, 2), add(2, 1);

    dfs1(1, 0, 1);
    dfs2(1, 1);

    build(1, 1, 2);

    cout << qSon(1) << '\n';
    return 0;
}

竟然没人用Python做

a, b = input().strip().split()
print(int(a)+int(b))

没有人使用线段树做这道题。

#include <bits/stdc++.h>
#define MAXN 200005
#define INF 1e9
#define mid(l, r) (l+r)/2
using namespace std;

int n, m;
int laz[MAXN * 4], w[MAXN * 4], a[MAXN];

bool InRange(int L, int R, int l, int r){
    return (l <= L) && (R <= r);
}

bool OutofRange(int L, int R, int l, int r){
    return (R < l) || (r < L);
}

void pushup(int u){
    w[u] = w[u*2] + w[u*2+1];
}

void build(int u, int L, int R){
    if (L == R){
        w[u] = a[L];
        return;
    }
    int M = mid(L, R);
    build(u*2, L, M);
    build(u*2+1, M+1, R);
    pushup(u);
}

void maketag(int u, int x){
    laz[u] = x;
    w[u] = w[u] + x;
}

void pushdown(int u){
    if (!laz[u]) return;
    maketag(u*2, laz[u]);
    maketag(u*2+1, laz[u]);
    laz[u] = 0;
}

int query(int u, int L, int R, int l, int r){
    if (InRange(L, R, l, r)){
        return w[u];
    }else if(!OutofRange(L, R, l, r)){
        int M = mid(L, R);
        pushdown(u);
        return query(u*2, L, M, l, r) + query(u*2+1, M+1, R, l, r);
    }else return 0;
}

void update(int u, int L, int R, int l, int r, int x){
    if (InRange(L, R, l, r)){
        maketag(u, x);
    }else if(!OutofRange(L, R, l, r)){
        int M = mid(L, R);
        pushdown(u);
        update(u*2, L, M, l, r, x);
        update(u*2+1, M+1, R, l, r, x);
        pushup(u);
    }else return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0), cerr.tie(0);
    
    cin>>n>>m;
    a[1] = n;
    build(1, 1, 2);
    update(1, 1, 2, 2, 2, m);
    cout<<query(1, 1, 2, 1, 2)<<endl;
    
    return 0;
}

从题目名就可以知道这道题其实就是一个简单的加法
题目描述里只不过是使用位运算实现加法

这里还有一种与题目不同的做法（GitHub Copilot写的）

// 用位运算实现加法
#include<bits/stdc++.h>
#define MAXN 100010
#define INF 1e9
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);cerr.tie(0);

    int a, b;
    cin>>a>>b;

    while(b != 0){
        int c = a ^ b;
        b = (a & b) << 1;
        a = c;
    }

    cout<<a<<endl;

    return 0;
}