这篇博客是第二天赛时写的。（恼）

T1

数学题。

肯定是想把 $k$ 质因数分解，然后找一找规律，发现对于一个最小的 $n$ 一定不包括除了 $k$ 有的质因子以外的其他质因子，因为其他质因子对是不是 $k$ 的倍数没有用。

$n^2$ 相当于把 $n$ 的所有质因子的指数乘了个 $2$，那么只要保证这个指数乘 $2$ 后大于等于 $k$ 的相同的质因子的指数，那么就是满足条件，要保证最小，直接把 $k$ 质因子指数除以二向上取整就好了。

发现数很大，没办法全部质因数分解。发现对于大于 $\sqrt{k}$ 的质因子的指数一定不大于一，那直接算到 $\sqrt{k}$，剩下的直接乘就可以了。

记得判无解情况，即 $n=k$ 时。

Code

#include <iostream>
#include <cstdio>

#define int long long

const int N=1e7+10;

using namespace std;

inline int read() {
    int f=1, x=0;
    char ch=getchar();
    while(ch>'9' || ch<'0') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return f*x;
}

inline void write(int x) {
    cout<<x; putchar('\n');
}

int k, tot, ans;
int prime[N], is_prime[N], cnt[N];

void pre_work() {
    for(int i=2;i<=N-5;i++) {
        if(!is_prime[i]) prime[++tot]=i;
        for(int j=1;j<=tot && prime[j]*i<=N-5;j++) {
            is_prime[prime[j]*i]=1;
            if(i%prime[j]==0) break;
        }
    }
}

inline int get_(int x,int k) {
    if(x%k==0) return x/k;
    else return (x/k)+1;
} 

inline int fpow(int x,int k) {
    int res=1;
    while(k) {
        if(k&1) res*=x;
        x=x*x;
        k>>=1;
    }
    return res;
}

signed main() {

    pre_work();

    k=read();
    
    int now=k;
    for(int i=1;i<=tot && prime[i]<=now;i++) {
        if(now%prime[i]==0) {
            while(now%prime[i]==0) {
                cnt[i]++;
                now/=prime[i];
            }
        }
    }

    int ans=now;
    for(int i=1;i<=tot;i++) {
        if(cnt[i]) {
            ans=ans*fpow(prime[i], get_(cnt[i], 2));
        }
    }
    if(ans==k) write(-1);
    else write(ans);

    return 0;
}

T2

Part1

发现值域只有 $[1,9]$，那么直接分讨，对于 $1, 5, 7$ 这三个数，和其他数的 $gcd$ 都为 $1$，又因为相同数没有区别，所以他们仨可以随便放。先分出来单独讨论。

Part2

剩下的 $2,3,4,6,8,9$，发现他们的公共质因子只有 $2,3$，而 $6$ 又都包含，说明 $6$ 不能换，只能在这里，那么若干个 $6$ 把序列分成了若干段，段与段之间互不影响。

考虑段内的贡献，发现公共质因子为 $2$ 的几个数相对位置不会变化，为 $3$ 的也不会变化，这两种数没有交集，互不影响，那么可以直接组合数算，设公共质因子为 $2$ 的数有 $n$ 个，为 $3$ 的数有 $m$ 个，那贡献就是 $\dbinom{n+m}{n}$，最后全部乘起来就好了。

对于 $1,5,7$ 的贡献，和上面差不多，设 $1$ 的总数为 $n$，当前数的个数为 $m$，贡献即为 $\dbinom{n+m}{n}$，$5$ 和 $7$ 也是一样的。

复杂度为 $\Theta(n)$。

Code

#include <iostream>
#include <cstdio>

#define int long long  

const int mod=998244353;
const int N=1e5+10;

using namespace std;

inline int read() {
    int f=1, x=0;
    char ch=getchar();
    while(ch>'9' || ch<'0') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return f*x;
}

inline void write(int x) {
    cout<<x; putchar('\n');
}

int n, tot, ans;
int a[N], cnt[N];
int fac[N], inv[N], invj[N];

void prework() {
    fac[0]=fac[1]=inv[0]=inv[1]=invj[0]=invj[1]=1;
    for(int i=2;i<=n+5;i++) {
        fac[i]=fac[i-1]*i%mod;
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        invj[i]=invj[i-1]*inv[i]%mod;
    }
    ans=1;
}

inline int C(int n,int m) {
    if(m>n) return 0;
    return fac[n]*invj[n-m]%mod*invj[m]%mod;
}

inline void solve(int l,int r) {
    if(l>=r) return;
    int sum1=0, sum2=0;
    for(int i=l;i<=r;i++) {
        if(a[i]%2==0) sum1++;
        else sum2++;
    }
    int sum=C(sum1+sum2, sum1);
    ans=(ans*sum)%mod;
}

signed main() {
    
    n=read();

    prework();

    for(int i=1;i<=n;i++) {
        int x=read();
        if(x==1 || x==5 || x==7) {
            cnt[x]++;
        }
        else a[++tot]=x;
    }
    
    int pre=1;
    for(int i=1;i<=tot;i++) {
        if(a[i]==6) {
            solve(pre, i-1);
            pre=i+1;
        }
    }
    solve(pre, tot);

    tot+=cnt[1], ans=(ans*C(tot, cnt[1]))%mod;
    tot+=cnt[5], ans=(ans*C(tot, cnt[5]))%mod;
    tot+=cnt[7], ans=(ans*C(tot, cnt[7]))%mod;

    write(ans);

    return 0;
}

T3

Part1

设最终的力量值为 $x$，首先发现将 $x$ 设置为原有的一条龙的力量值一定更优，证明考虑移动 $x$，在龙与龙之间时的图像是一条直线，那么最值一定出在一个拐点上，也就是原有的一条龙的力量值。

考虑刻画出函数图像，对于单个一条龙，函数图像一定是一个凸函数，又因为凸函数也是凸函数，那么多条龙的函数的加和也一定是凸函数，那么可以直接三分找到最值，只不过复杂度为 $\Theta(n\log^2n)$，好像可以过。

Part2

考虑那个凸函数各部分的斜率，发现越接近答案，斜率越小，可以通过这个直接求出答案拐点的排名。

设答案拐点前有 $P$ 个点，那么从第 $P$ 个点到第 $P+1$ 个点的斜率一定是最小的，单位变化量也是最小的。想象一个点在图像上移动，每移动 $1$ 的力量值，$\Delta f(x)=a\times P-b\times(i-P) \leqslant 0$，解得 $P \leqslant \dfrac{b\times i}{a+b}$，这个 $P$ 一定是最大的，所以取等，答案拐点的排名即为 $P+1$。

Part3

代码实现上，先离散化，因为要动态查询排名为 $K$ 的值，快速求出以 $x$ 为最终的力量值的总代价，所以直接权值线段树就行了，然后一个一个地加，一个一个地求，复杂度 $\Theta(n\log n)$。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>

#define int long long

const int N=1e6+10;

using namespace std;

inline int read() {
    int f=1, x=0;
    char ch=getchar();
    while(ch>'9' || ch<'0') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return f*x;
}

inline void write(int x) {
    cout<<x; putchar('\n');
}

int n, a, b;
int d[N], mp[N], ans[N];

map <int,int> Kth;

 struct Tree {
        int sum, size;
    }t[N<<2];

struct Seg_Tree {

    inline Tree merge(Tree ls, Tree rs) {
        Tree res=(Tree){0, 0};
        res.size=ls.size+rs.size;
        res.sum=ls.sum+rs.sum;
        return res;
    }
   
    inline void push_up(int k) {
        t[k]=merge(t[k<<1], t[k<<1|1]);
    }

    void change(int k,int l,int r,int pos,int val) {
        if(l==r) {
            t[k].sum+=val*mp[l];
            t[k].size+=val;
            return;
        }
        int mid=(l+r)>>1;
        if(pos<=mid) change(k<<1, l, mid, pos, val);
        else change(k<<1|1, mid+1, r, pos, val);
        push_up(k);
    }

    int find(int k,int l,int r,int K) {
        if(l==r) return l;
        int mid=(l+r)>>1;
        if(t[k<<1].size>=K) return find(k<<1, l, mid, K);
        else return find(k<<1|1, mid+1, r, K-t[k<<1].size);
    }

    Tree query(int k,int l,int r,int L,int R) {
        if(L<=l && r<=R) return t[k];
        int mid=(l+r)>>1;
        Tree ls=(Tree){0, 0}, rs=(Tree){0, 0};
        if(L<=mid) ls=query(k<<1, l, mid, L, R);
        if(R>mid) rs=query(k<<1|1, mid+1, r, L, R);
        return merge(ls, rs);
    }
}T;

signed main() {

    n=read(), a=read(), b=read();
    for(int i=1;i<=n;i++) {
        d[i]=read();
        mp[i]=d[i];
    }

    sort(mp+1, mp+n+1);
    int Len=unique(mp+1, mp+n+1)-mp-1;
    for(int i=1;i<=Len;i++) Kth[mp[i]]=i;

    for(int i=1;i<=n;i++) {
        T.change(1, 1, n, Kth[d[i]], 1);
        int p=(b*i)/(a+b);
        int pos=T.find(1, 1, n ,p+1);
        Tree ll=(Tree){0, 0}, rr=(Tree){0, 0};
        if(pos-1>=1) ll=T.query(1, 1, n, 1, pos-1);
        if(pos+1<=n) rr=T.query(1, 1, n ,pos+1, n);
        ans[i]=(mp[pos]*ll.size-ll.sum)*a+(rr.sum-mp[pos]*rr.size)*b;
    }
    
    for(int i=1;i<=n;i++) write(ans[i]);

    return 0;
}

T4

$T4$ 的难度有点水吧？

Part1

根据初中数学知识：

$a^x·a^y=a^{x+y}$

$(a_1+a_2+\dots+a_n)·(b_1+b_2+\dots+b_m)=a_1b_1+a_1b_2+\dots+a_1b_m+a_2b_1+a_2b_2+\dots+a_nb_m$

那么可以直接把贡献拆开，$u$ 的一部分，$v$ 的一部分，$u$ 和 $v$ 之间的路径。最后直接乘起来就行了。

Part2

设 $f_i=\sum_{u\in sutree_i}2^{dis_{u,i}}$，$ g_i=\sum_{u=1}^{n}dis_{u,i}$。$f_i$ 就是它的子树内的点对他的贡献，$g_i$ 是所有点对它的贡献。

分为两种情况：

第一种情况，$u$ 和 $v$ 都不是 $lca$，那么经过 $u$ 和 $v$ 的路径的两个端点一定一个在 $u$ 的子树，一个在 $v$ 的子树，那么答案就是 $f_u\times f_v \times 2^{dis_u,v}$，这个好算。

第二种情况，$u$ 和 $v$ 其中有一个是 $lca$，默认非 $lca$ 的那个点为 $u$，那么经过 $u$ 和 $v$ 的路径的两个端点，一个在 $u$ 子树内，另一个在把 $u$ 所在的 $lca$ 的子树的所有节点刨除后，剩下的其他节点上，画一画图就明白了，我们把 $u$ 所在的 $lca$ 的子树的根节点称为 $clca$，那么答案就是 $f_u \times (g_{lca}-2\times f_{clca} )\times 2^{dis_{u,lca}}$。

Part3

实现上，可以用换根$dp$ 在 $\Theta(n)$ 复杂度内求出 $f_i$ 和 $g_i$。（也可以用点分治，只不过复杂度劣一些，$\Theta(n\log n)$ 加上大常数，可能过不去，而且还相对难写）

求 $lca$ 和 $clca$ 可以用树剖（倍增常数太大），也可以用 $Tarjan$ 离线求。

如何用树剖求 $clca$，先找到 $lca$，然后从 $u$ 往 $lca$ 跳，记录当前链的链顶，跳到链顶相同后开始分讨。

$u=lca$，也就是上一条链的链顶的父亲是 $lca$，$clca$ 和 $lca$ 不在同一条重链上，那么上一条链的链顶就是 $clca$。
剩下的情况就是 $clca$ 和 $lca$ 在同一条重链上，因为重链上的 $dfs$序是连续的，那么 $clca$ 的 $dfs$序就是 $lca$ 的下一位。预处理时记录一下 $dfs$序就可以了。

复杂度为 $\Theta(q\log n)$，轻微卡常。

Code

#include <iostream>
#include <cstdio>

#define rint register int
#define ll long long

const int N=1e6+10;
const ll mod=998244353;

using namespace std;

inline int read() {
    int f=1, x=0;
    char ch=getchar();
    while(ch>'9' || ch<'0') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return f*x;
}

inline void write(ll x) {
    cout<<x; putchar('\n');
} 

int n, cnt_edge;
struct edge {
    int next ,to;
}e[N<<1];
int head[N];

inline void add_edge(int u,int v) {
    e[++cnt_edge].to=v;
    e[cnt_edge].next=head[u];
    head[u]=cnt_edge;
}

ll vs[N], vr[N];
void dfs1(int now,int fa) {
    vs[now]=1;
    for(rint i=head[now];i;i=e[i].next) {
        int v=e[i].to;
        if(v==fa) continue;
        dfs1(v, now);
        vs[now]=(vs[now]+vs[v]*2ll)%mod;
    }
}

void dfs2(int now,int fa) {
    ll sum=(vr[fa]+mod-vs[now]*2ll)%mod;
    vr[now]=(vs[now]+sum*2ll)%mod;
    for(rint i=head[now];i;i=e[i].next) {
        int v=e[i].to;
        if(v==fa) continue;
        dfs2(v, now);
    }
}

int tim, dfn[N], mp[N];
int dep[N], siz[N], fa[N], top[N], son[N];
struct Heavy {
    void dfs1(int now,int father) {
        dep[now]=dep[father]+1, siz[now]=1;
        fa[now]=father, son[now]=0;
        int maxson=-1;
        for(rint i=head[now];i;i=e[i].next) {
            int v=e[i].to;
            if(v==father) continue;
            dfs1(v, now);
            siz[now]+=siz[v];
            if(siz[v]>maxson) {
                maxson=siz[v], son[now]=v;
            }
        }
    }
    void dfs2(int now,int topf) {
        dfn[now]=++tim, mp[tim]=now;
        top[now]=topf;
        if(son[now]) dfs2(son[now], topf);
        for(rint i=head[now];i;i=e[i].next) {
            int v=e[i].to;
            if(v==son[now] || v==fa[now]) continue;
            dfs2(v, v);
        }
    }
   
    inline int LCA(int x,int y) {
        while(top[x]!=top[y]) {
            if(dep[top[x]] < dep[top[y]]) x^=y, y^=x, x^=y;
            x=fa[top[x]];
        }
        if(dep[x] > dep[y]) x^=y, y^=x, x^=y;
        return x;
    }

    inline int CLCA(int x,int y) {
        int topf=0;
        while(top[x]!=top[y]) {
            topf=top[x];
            x=fa[top[x]];
        }
        if(x==y) return topf;
        else if(fa[x]==y) return x;
        else return mp[dfn[y]+1];
    }
}H;

ll power[N];
void prework() {
    dfs1(1, 0);
    vr[1]=vs[1];
    for(rint i=head[1];i;i=e[i].next) {
        int v=e[i].to;
        dfs2(v, 1);
    }
    power[0]=1;
    for(rint i=1;i<=n+5;++i) {
        power[i]=power[i-1]*2ll%mod;
    }
    H.dfs1(1, 0);
    H.dfs2(1, 1);
}

signed main() {
    
    n=read();
    for(rint i=1;i<n;++i) {
        int u=read(), v=read();
        add_edge(u, v);
        add_edge(v, u);
    }

    prework();

    int q=read();
    for(rint tur=1;tur<=q;++tur) {
        int u=read(), v=read();
        int lca=H.LCA(u, v);
        int dis=dep[u]+dep[v]-2ll*dep[lca];
        ll ans=power[dis];
        if(u==lca || v==lca) {
            if(u==lca) u=v;
            int clca=H.CLCA(u, lca);
            ans=(ans*vs[u]%mod*((vr[lca]-vs[clca]*2ll+mod)%mod))%mod;
        }
        else ans=ans*vs[u]%mod*vs[v]%mod;
        write((ans+mod)%mod);
    }
    
    return 0;
}