虽然是正解，但是我三分敲挂了，悲
A. 上海
对于每个数，\(O(\sqrt n)\) 地分解质因数，对于每一个质数，符合要求的 \(n\) 最小需要为 \(\lceil num \rceil\)。
如果乘完后的 \(n\) 等于原数，那么无解。
code
#include<bits/stdc++.h>
using namespace std;
const long long M=1e6+10;
long long n=1,k,kk,cnt;
long long p[M],num[M];
inline long long read(){
long long x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
inline bool check(){
for(long long i=1;i<=cnt;i++){
if(num[i]&1){
n=n*pow(p[i],(num[i]+1)/2);
}
else {
n=n*pow(p[i],num[i]/2);
}
}
if(n==kk){
return 0;
}
cout<<n<<'\n';
return 1;
}
int main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
k=read(); kk=k;
for(long long i=2;i<=sqrt(k);i++){
if(k%i==0){
p[++cnt]=i;
while(k%i==0){
num[cnt]++;
k=k/i;
}
}
}
if(k!=1){
p[++cnt]=k; num[cnt]=1;
}
if(!check()){
cout<<-1<<'\n';
}
return 0;
}
B. 华二
或许下次可以尝试一下
由于 \(a_i \leqslant 9\)，所以可以考虑一下值的性质。
不难发现，\(\{1,5,7\}\) 与所有数的 \(\gcd\) 都为 \(1\)，所以可以交换到任何位置，先提出来最后直接插，注意去掉重复情况。
然后发现，\(6\) 与其他数的 \(\gcd\) 都不为 \(1\)，因此可以利用 \(6\) 将整个区间分成一些段。
剩下的可以分开 \(\{2,4,8\}\) 和 \(\{3,9\}\) ，两个集合相互之间可以互相交换，所以相对位置是不发生变化，可以直接用组合数计算。
code
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
const long long M=1e5+10;
long long n,cnt,tot,ans=1;
long long a[M],f[M],g[M];
long long num[10];
map<long long,long long>mp;
vector<long long>h[M];
inline long long read(){
long long x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
inline long long po(long long x,long long k){
long long ans=1;
while(k){
if(k&1){
ans=ans*x%mod;
}
x=x*x%mod;
k=k>>1;
}
return ans;
}
inline void pre(){
f[0]=g[0]=1;
for(long long i=1;i<=n;i++){
f[i]=f[i-1]*i%mod;
}
g[n]=po(f[n],mod-2);
for(long long i=n-1;i>=1;i--){
g[i]=g[i+1]*(i+1)%mod;
}
}
inline long long C(long long n,long long m){
return f[n]*g[m]%mod*g[n-m]%mod;
}
int main(){
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
n=read();
pre();
for(long long i=1;i<=n;i++){
long long x=read();
if(x==1||x==5||x==7){
tot++;
}
else {
if(x==6){
cnt++;
}
else {
h[cnt].push_back(x);
}
}
num[x]++;
}
for(long long i=0;i<=cnt;i++){
long long x=0,y=0;
for(long long j=0;j<h[i].size();j++){
long long res=h[i][j];
if(res&1){
x++;
}
else {
y++;
}
}
ans=ans*C(x+y,x)%mod;
}
ans=ans*C(n,tot)%mod;
ans=ans*f[tot]%mod*g[num[1]]%mod*g[num[5]]%mod*g[num[7]]%mod;
cout<<ans<<'\n';
return 0;
}
C. 高爸
就是正解，就是没调出来
对于每一条龙，它的力量值是一个凹函数，所以所有的龙的函数加起来也是一个凹函数，这个可以三分求。
对于一个力量值 \(x\)，可以将所有的龙分为力量值小于它的和力量值大于它的，所以它的贡献就是需要修改的力量值乘上对应的点数。
求需要修改的力量值要用到个数和总和，可以写权值树状数组，权值线段树，平衡树。
注意要用 \(unsigned\ long\ long\)。
code
#include<bits/stdc++.h>
using namespace std;
const long long M=1e5+10;
struct abc{
long long num,sum;
}t[M];
long long n,a,b,tot;
long long w[M];
long long va[M];
long long pre[M];
long long mp[M];
inline long long read(){
long long x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
inline long long lowbit(long long x){
return (x&(-x));
}
inline void update(long long x){
long long wei=mp[x];
while(wei<=tot){
t[wei].num++;
t[wei].sum+=w[x];
wei+=lowbit(wei);
}
}
inline pair<long long,long long> query(long long x){
long long ans1=0;
long long ans2=0;
while(x){
ans1+=t[x].num;
ans2+=t[x].sum;
x-=lowbit(x);
}
return make_pair(ans1,ans2);
}
int main(){
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
n=read(); a=read(); b=read();
for(long long i=1;i<=n;i++){
w[i]=read(); va[i]=w[i];
pre[i]=pre[i-1]+w[i];
}
sort(va+1,va+n+1);
tot=unique(va+1,va+n+1)-va-1;
for(long long i=1;i<=n;i++){
mp[i]=lower_bound(va+1,va+tot+1,w[i])-va;
}
cout<<0<<'\n';
update(1);
for(long long i=2;i<=n;i++){
update(i);
long long l=1,r=tot;
unsigned long long ans=0;
while(l<=r){
long long len=(r-l)/3;
long long mid1=l+len;
pair<long long,long long> p1=query(mid1);
unsigned long long res1=(p1.first*va[mid1]-p1.second)*a+(pre[i]-p1.second-(i-p1.first)*va[mid1])*b;
long long mid2=r-len;
pair<long long,long long> p2=query(mid2);
unsigned long long res2=(p2.first*va[mid2]-p2.second)*a+(pre[i]-p2.second-(i-p2.first)*va[mid2])*b;
if(res1<=res2){
r=mid2-1;
ans=res1;
}
else {
l=mid1+1;
ans=res2;
}
}
cout<<ans<<'\n';
}
return 0;
}
D. 金牌
树形 DP，还好没敲点分治
规定 \(f_i\) 为以 \(i\) 为根的子树到 \(i\) 的贡献和（不包括 \(i\) ）。
规定 \(g_i\) 为以 全部节点除去以 \(i\) 为根的子树的贡献和（不包括 \(i\) ）。
\[\begin{aligned}
f&_i=f_{son_i}\times 2+2\\
g&_i=g_{fa_i}\times 2+2+(f_{fa_i}-f_i\times 2-2)\times 2
\end{aligned}
\]
对于一组询问 \(x,y\)（钦定 \(x\)的深度小于 \(y\) 的深度），可以分为两类，\(x\) 为 \(y\) 的祖先，和 \(x\) 不是 \(y\) 的祖先。
若 \(x\) 是 \(y\) 的祖先，设 \(res\) 为 \(x\) 在 \(x\) 到 \(y\) 路径上的儿子。
所以它的答案就是 \((f_i+1)\times g_{res}\times 2^{dis_{y,res}}\)。
另一种情况比较简单，就是 \((f_x+1)\times (f_y+1)\)。
记得卡常。
code
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
const int M=1e6+10;
struct abc{
int y,to;
}e[M<<1];
int n,q,tot,cnt;
int in[M],out[M],d[M];
int head[M];
int fa[M],son[M],top[M],size[M],deep[M];
long long f[M],g[M],p[M];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
inline void output(long long x){
if(x<0){
x*=-1;
putchar('-');
}
if(x>9){
output(x/10);
}
putchar(x%10+'0');
return;
}
inline long long Mod(long long x){
return x>mod?x-mod:x;
}
inline void add(int x,int y){
e[++cnt].y=y; e[cnt].to=head[x]; head[x]=cnt;
}
void dfs1(int x,int father){
fa[x]=father;
size[x]=1; deep[x]=deep[father]+1;
for(int i=head[x];i;i=e[i].to){
int y=e[i].y;
if(y!=father){
dfs1(y,x);
f[x]=Mod(f[x]+f[y]*2%mod+2);
size[x]+=size[y];
if(size[son[x]]<size[y]){
son[x]=y;
}
}
}
}
void dfs2(int x,int tp){
if(x==1){
g[x]=0;
}
else {
g[x]=Mod(g[fa[x]]*2%mod+2+Mod(f[fa[x]]-f[x]*2%mod-2+mod)*2%mod);
}
top[x]=tp;
in[x]=++tot; d[tot]=x;
if(son[x]){
dfs2(son[x],tp);
}
for(int i=head[x];i;i=e[i].to){
int y=e[i].y;
if(y!=fa[x]&&y!=son[x]){
dfs2(y,y);
}
}
out[x]=tot;
}
inline int lca(int x,int y){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]){
swap(x,y);
}
x=fa[top[x]];
}
return deep[x]>deep[y]?y:x;
}
inline int get(int x,int y){
int res=0;
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]){
swap(x,y);
}
res=top[x];
x=fa[top[x]];
}
if(x==y){
return res;
}
return deep[x]>deep[y]?d[in[y]+1]:d[in[x]+1];
}
int main(){
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
n=read();
for(int i=1;i<n;i++){
int x=read(),y=read();
add(x,y); add(y,x);
}
dfs1(1,0); dfs2(1,1);
p[0]=1;
for(int i=1;i<=n;i++){
p[i]=p[i-1]*2%mod;
}
q=read();
while(q--){
int x=read(),y=read();
if(deep[x]>deep[y]){
swap(x,y);
}
int an=lca(x,y);
long long mid=p[deep[x]+deep[y]-deep[an]-deep[an]];
long long ans=0;
if(in[x]<=in[y]&&out[y]<=out[x]){
int res=get(x,y);
ans=g[res]*mid%mod*(f[y]+1)%mod*499122177%mod;
}
else {
ans=(f[x]+1)*(f[y]+1)%mod*mid%mod;
}
output(ans);
putchar('\n');
}
exit(0);
}