这篇博客是第二天赛时写的。（恼）
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;
}