T1

列个式子（或者直接猜）容易发现，小的放前面比放后面更优，所以sort一遍，前一半加，后一半乘即可

T2

将每个数表示成的形式，于是直接累加b即可比大小

注意细节，比如可能爆 long long

T3

画图可以发现答案只会在 ~ 之间，先丢掉，对剩下的所有点极角排序，分情况讨论：

1. 输出0
2. 和某个的直线过，输出1，可以二分找到这个点
3. 假设所有点与在同一条直线上，那么由于步骤2没有输出1，一定无解，输出-1
4. 否则与的连线至少有两种，画图可以发现如果一定输出2
5. 如果，只有当询问点，和两个点构成了一个平行四边形时会输出3，否则输出2

#include<bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
int n,q;
struct pts
{
    ll x,y;
    pts() { }
    pts(ll x,ll y) : x(x),y(y) { }
    pts operator + (const pts &a)const { return pts(x + a.x,y + a.y); }
    pts operator - (const pts &a)const { return pts(x - a.x,y - a.y); }
    ll operator ^ (const pts &a)const { return x * a.y - y * a.x; }
    bool operator == (const pts &a)const { return (x == a.x) && (y == a.y); }
    bool operator < (const pts &a)const
    {
        return ((*this) ^ a) > 0;
    }
}pt[N];

bool sm(pts a,pts b) { return ((a ^ b) == 0); }

int main()
{
    freopen("c12.in","r",stdin);
    freopen("c12.out","w",stdout);
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld%lld",&pt[i].x,&pt[i].y);
        if(pt[i].x == 0 && pt[i].y == 0) --i,--n;
    }
    sort(pt + 1,pt + n + 1);
    bool lin = sm(pt[1],pt[n]);//所有的点都在同一条线上

    while(q--)
    {
        pts a; scanf("%lld%lld",&a.x,&a.y);
        if(a.x == 0 && a.y == 0) { puts("0"); continue; }

        int it = lower_bound(pt + 1,pt + n + 1,a) - pt;
        if(1 <= it && it <= n && sm(pt[it] , a)) { puts("1"); continue; }

        if(lin) { puts("-1"); continue; }

        if(n > 2) { puts("2"); continue; }

        if(a == (pt[1] + pt[2])) puts("3");
        else puts("2");
    }
    return 0;
}

T4

如果分解出来的序列存在一个，那么将换成一定更优（前者能组合出来的lcm后者都可以组合出来，而且后者的和不大于前者）

于是分解出来的每个数一定是1或者的形式，线筛出n以内的质因子，背包DP即可，dp的时候因为取了模不能比大小，所以要取个log

（虽然质因子可能很多，但是可以发现不同质因子的贡献都是一样的，所以质因子越小越好，实际上能用的质因子只会有一百多个）

也可以打表搞出来

#include<bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
int n;
int p[N],isnotp[N],cnt;
pair<double,ll> f[N];

void init(int maxn)
{
    for(int i=2;i<=maxn;++i)
    {
        if(!isnotp[i]) p[++cnt] = i;
        for(int j=1;j<=cnt&&(ll)p[j]*i<=maxn;++j)
        {
            isnotp[p[j] * i] = 1;
            if(i % p[j] == 0) break;
        }
    }
}
int main()
{
    //freopen("d10.in","r",stdin);
    //freopen("d10.out","w",stdout);
    scanf("%d",&n);
    init(n);
    int now = 0,sum = 0;
    for(int i=1;i<=cnt;++i)
    {
        now = i;
        sum += p[i];
        if(sum > n) break;
    }
    f[0].first = 0; f[0].second = 1;
    for(int i=1;i<=now;++i)
    {
        for(int j=n;j>=1;--j)
        {
            ll t = p[i],pp = p[i];
            for(int k=1;t <= j;++k,pp*=p[i],t += pp)
            {
                pair<double,ll> nxt = make_pair(f[j - t].first + log2(k + 1),f[j - t].second * (k + 1) % mod);
                f[j] = max(f[j] , nxt);
            }
        }
    }
    pair<double,ll> ans; ans.first = -1;
    for(int i=0;i<=n;++i) ans = max(ans,f[i]);
    printf("%lld\n",ans.second);
    return 0;
}

T5

将一个点拆成入点和出点，入点向出点连q条边，流量为1，费用分别为，源点向所有连一条流量为1费用为0的边，向汇点连一条流量为1费用为0的边，原图的边连接出点和入点，流量为inf，费用为0，然后跑最小费用最大流即可

#include<bits/stdc++.h>
#define N 405
#define M 200005
using namespace std;
int n,m,q,s,t;
int in[N],out[N],a[N],b[N];
int dis[N],flow[N],exist[N];
int pre[N],preedge[N];

struct Edge
{
    int next,to,flow,dis;
}edge[M << 1]; int head[N],cnt = 1;
void add_edge(int from,int to,int flow,int dis)
{
    edge[++cnt].next = head[from];
    edge[cnt].to = to;
    edge[cnt].flow = flow;
    edge[cnt].dis = dis;
    head[from] = cnt;
}
void add(int from,int to,int flow,int dis)
{
    add_edge(from,to,flow,dis);
    add_edge(to,from,0,-dis);
}

bool spfa(int s,int t)
{
    memset(dis,100,sizeof(dis));
    memset(flow,100,sizeof(flow));
    memset(exist,0,sizeof(exist));
    queue<int> q;
    pre[t]=-1; exist[s]=1; dis[s]=0; q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();exist[u]=0;
        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(edge[i].flow>0&&dis[v]>dis[u]+edge[i].dis)
            {
                dis[v]=dis[u]+edge[i].dis;
                flow[v]=min(edge[i].flow,flow[u]);
                pre[v]=u;
                preedge[v]=i;
                if(!exist[v])
                {
                    exist[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return pre[t]!=-1;
}
int MCMF()
{
    int ret = 0;
    while(spfa(s,t))
    {
        ret += flow[t] * dis[t];
        int now = t;
        while(now!=s)
        {
            edge[preedge[now]].flow -= flow[t];
            edge[preedge[now]^1].flow += flow[t];
            now=pre[now];
        }
    }
    return ret;
}

int main()
{
//    freopen("9.in","r",stdin);
//    freopen("e9.out","w",stdout);
    scanf("%d%d%d",&n,&m,&q);
    s = 0,t = N - 1;
    for(int i=1;i<=n;++i)
    {
        int a,b; scanf("%d%d",&a,&b);
        for(int j=1;j<=q * 2;++j) add(i,i + n,1,a + (j - 1) * b);
    }
    for(int i=1;i<=m;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x + n,y,q * 2,0);
        add(y + n,x,q * 2,0);
    }
    for(int i=1;i<=q;++i)
    {
        int x; scanf("%d",&x);
        add(s,x,1,0);
    }
    for(int i=1;i<=q;++i)
    {
        int x; scanf("%d",&x);
        add(x + n,t,1,0);
    }
    printf("%d\n",MCMF());
    return 0;
}

T6

由于加和乘运算可以表示成的形式，可以通过维护a和b来表示一块运算，合并可以做到，其逆运算可以列个式子做

对于每一个点，预处理出它到根节点这段路径， ~ 时，向上走和向下走的表达式，这个表达式可以从d祖先处转移过来做到计算（可以理解为前缀和一样的东西）；时用这个表达式做差就能得到一条链的表达式，时直接暴力算就行了

跳k级祖先：可以倍增或者长链剖分求（实测加了个深度剪枝的倍增跑得比长链剖分还快）

根据跳k级祖先的实现方法，总复杂度为或

如果被卡常了可以调一下块的大小，我是开的150过的

如果有把std按在地上锤的方法请联系出题人

#include<bits/stdc++.h>
#define N 100005
#define pr pair<int,int>
using namespace std;
const int mod = 998244353;
const int sqr = 150;
int n,q,lg[N];
int fa[N],dep[N],f[N][18];
int st[N],top;

vector<int> s[N];
pr a[N],up[N][sqr + 5],dw[N][sqr + 5];

inline int qp(int a,int b) { int ret=1; for(;b;b>>=1,a=1ll*a*a%mod) if(b & 1) ret=1ll*ret*a%mod; return ret; }
inline pr merge(pr a,pr b) { return make_pair(1ll * a.first * b.first % mod , (1ll * a.second * b.first + b.second) % mod); }

inline int kfa(int rt,int k)
{
    for(register int i=lg[k];i>=0;--i) if(k >> i & 1) rt = f[rt][i];
    return rt;
}
inline int lca(int x,int y)
{
    if(dep[x] < dep[y]) swap(x,y);
    for(int i=17;i>=0;--i) if(dep[f[x][i]] >= dep[y]) x = f[x][i];
    if(x == y) return x;
    for(int i=17;i>=0;--i) if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
    return f[x][0];
}

void get(int rt)
{
    int x = rt;
    for(int d=1;d<=sqr;++d)
    {
        x = fa[x];

        up[rt][d] = a[rt];
        if(x) up[rt][d] = merge(up[rt][d] , up[x][d]);
        dw[rt][d] = a[rt];
        if(x) dw[rt][d] = merge(dw[x][d] , dw[rt][d]);
    }
}
void dfs(int rt)
{
    dep[rt] = dep[fa[rt]] + 1;
    f[rt][0] = fa[rt];
    for(int i=1;i<18;++i) f[rt][i] = f[f[rt][i - 1]][i - 1];

    get(rt);

    for(auto v : s[rt])
    {
        if(v == fa[rt]) continue;
        fa[v] = rt; dfs(v);
    }
}

int brute(int x,int y,int c,int d)
{
    int l = lca(x,y);
    pr ret = make_pair(1,0);
    int cnt = 0;
    while(1)
    {
        ret = merge(ret , a[x]);
        if(dep[kfa(x,d)] >= dep[l]) x = kfa(x,d);
        else break;
    }
    int fir = dep[l] + (d - (dep[x] - dep[l]));
    fir = dep[y] - fir;
    for(;fir >= 0;fir -= d) ret = merge(ret,a[kfa(y,fir)]);
    return (1ll * c * ret.first % mod + ret.second) % mod;
}
int solve(int x,int y,int c,int d)
{
    pr ret = make_pair(1,0);
    int A,B,C,D;
    int l = lca(x,y),tmp = kfa(x,((dep[x] - dep[l]) / d + 1) * d);

    A = up[tmp][d].first; B = up[tmp][d].second;
    C = up[x][d].first; D = up[x][d].second;
    if(!tmp) ret = up[x][d];
    else ret = make_pair(1ll * C * qp(A,mod - 2) % mod , 1ll * (D - B) * qp(A,mod - 2) % mod);

    int nxt = ((dep[x] - dep[l]) / d + 1) * d - (dep[x] - dep[l]) + dep[l];
    if(nxt <= dep[y])
    {
        y = kfa(y,dep[y] - (nxt + ((dep[y] - nxt) / d * d)));
        tmp = kfa(y,((dep[y] - dep[l] - 1) / d + 1) * d);
        A = dw[tmp][d].first; B = dw[tmp][d].second;
        C = dw[y][d].first; D = dw[y][d].second;

        if(!tmp) ret = merge(ret , dw[y][d]);
        else ret = merge(ret , make_pair(1ll * C * qp(A,mod - 2) % mod , (D - 1ll * B * C % mod * qp(A,mod - 2) % mod) % mod));
    }

    return (1ll * c * ret.first % mod + ret.second) % mod;
}

int main()
{
    //freopen("f8.in","r",stdin);
    //freopen("f8.out","w",stdout);
    lg[0] = -1; for(int i=1;i<N;++i) lg[i] = lg[i >> 1] + 1;
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;++i)
    {
        int x,y; scanf("%d%d",&x,&y);
        s[x].push_back(y);
        s[y].push_back(x);
    }
    for(int i=1;i<=n;++i)
    {
        char op[2]; int x;
        scanf("%s%d",op,&x);
        if(op[0] == '+') a[i] = make_pair(1,x);
        else a[i] = make_pair(x,0);
    }
    dfs(1);
    while(q--)
    {
        int x,y,c,d;
        scanf("%d%d%d%d",&x,&y,&c,&d);
        if(d > sqr) printf("%d\n",(brute(x,y,c,d) % mod + mod) % mod);
        else printf("%d\n",(solve(x,y,c,d) % mod + mod) % mod);
    }
    return 0;
}