赛后关网罪大恶极
T1 上海
直接算数基本定理
点击查看代码
#include<bits/stdc++.h>
typedef int count ;
typedef long long value;
inline value read(){
count f(1);
value x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
void write(value x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
#define debug(x) std::cout<<"###"<<x<<std::endl;
#define maxn 1000010
value k;
value p[maxn],c[maxn],cnt;
bool isnt[maxn];
value prime[maxn],num;
inline value kuai(value base,count x){
value val=1;
while(x){
if(x&1) val=val*base;
base=base*base;
x>>=1;
}
return val;
}
int main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
k=read();
for(count i=2;i<=sqrt(k);i++){
if(!isnt[i]){
prime[++num]=i;
}
for(count j=1;j<=num && i*prime[j]<=sqrt(k);j++){
isnt[i*prime[j]]=1;
if(i%prime[j]==0){
break;
}
}
}
for(count i=1;i<=num;i++){
count now=prime[i];
// debug("OK")
if(k%now==0){
// debug(now)
p[++cnt]=now;
while(k%now==0){
c[cnt]++;
k/=now;
}
}
}
if(k!=1){
p[++cnt]=k;
c[cnt]=1;
k=1;
}
bool flag=0;
for(count i=1;i<=cnt;i++){
if(c[i]>1){
flag=1;
break;
}
}
if(!flag ){
write(-1);
return 0;
}
value ans=1;
for(count i=1;i<=cnt;i++){
ans=(ans*kuai(p[i],(c[i]>>1)+(c[i]&1)));
}
write(ans);
return 0;
}
T2 华二
赛时没想到6该怎么办。悲。
首先除了6和157之外，其他的数可以分为能被2整除的和能被3整除的。这两段相当于两个顺序确定的序列合并保持相对顺序不变 \(\dbinom{a+b}{a}\)。
这些显然不能和6换，相对6位置不变，就把整个序列按6分成一段一段的。
其他的157也看作不能交换得按有顺序插入。
点击查看代码
#include<bits/stdc++.h>
typedef int count ;
typedef long long value;
inline value read(){
count f(1);
value x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
void write(value x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
#define debug(x) std::cout<<"###"<<x<<std::endl;
#define mod 998244353
#define maxn 100010
count n;
value a[maxn];
value jie[maxn<<1],ni[maxn<<1];
inline value kuai(value base,value x){
value val=1;
while(x){
if(x&1) val=val*base%mod;
base=base*base%mod;
x>>=1;
}
return val;
}
inline value suan(value n,value m){
value val=jie[n]*ni[m]%mod*ni[n-m]%mod;
return (val? val:1);
}
int main(){
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
n=read();
for(count i=1;i<=n;i++){
a[i]=read();
}
jie[0]=ni[0]=1;
for(count i=1;i<=n+n+5;i++){
jie[i]=jie[i-1]*i%mod;
ni[i]=ni[i-1]*kuai(i,mod-2)%mod;
// debug(ni[i])
}
value ans=1;
value all=0;
for(count i=0;i<=n;i++){
value cnt2=0,cnt3=0;
while(a[i+1]!=6 && i<n){
i++;
if(a[i]==2 || a[i]==4 || a[i]==8) cnt2++;
if(a[i]==3 || a[i]==9) cnt3++;
}
all+=cnt2+cnt3+(a[i+1]==6);
ans=(ans*suan(cnt2+cnt3,cnt2))%mod;
}
count cnt1=0,cnt5=0,cnt7=0;
for(count i=1;i<=n;i++){
if(a[i]==1) cnt1++;
if(a[i]==5) cnt5++;
if(a[i]==7) cnt7++;
}
ans=(ans*suan(all+cnt1,all))%mod;
all+=cnt1;
ans=(ans*suan(all+cnt5,all))%mod;
all+=cnt5;
ans=(ans*suan(all+cnt7,all))%mod;
write(ans),putchar('\n');
return 0;
}
T3 高爸(够吧
赛时没啥太好的思路，只会打70pts的还挂了特殊性质。枚举值域的做法。
首先设 \(x\) 为比当前值 \(val\) 大的有多少个能量值，\(sum_x\) 为它们到 \(val\) 的距离之和，\(y\)，\(sum_y\) 小但是同理。\(ans=asum_y+bsum_x\)。
然后我们给 \(val\) 增加 1。\(ans=a(sum_x-x)+b(sum_y+y)\)。\(\Delta=-bx+ay\)。在任意的确定的两个能量值之间，这个值肯定是不变的，所以如果它是负的就得让它负的更多，所以一定要到它的端点，所以最优决策一定在某个确定的龙的能量值的位置。
好吧这是赛时就知道的，但是只是证了在龙的能量值的位置取到最优。没往后想。
所以如果我们减少到了下一个能量值，此时 \(x,y\) 发生了变化。\(\Delta=-b(x-1)+a(y+1)\)，因为减少会更优我们才让它减少，我们钦定它在变化前是个负数。它变得更大了。相当于斜率变大了。
所以这个函数的图像大概就：
可以按斜率使用二分（好像要用平衡树维护吧大概）或者三分
我按值域三分没卡过去(
70pts，2000~2700ms跑完
#include<bits/stdc++.h>
typedef int count ;
typedef long long value ;
inline value read(){
count f(1);
value x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
void write(value x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
#define debug(x) std::cerr<<"###"<<x<<std::endl;
#define maxn 100010
count n,m;
value a,b;
value x[maxn],zhen[maxn];
value book[maxn];
count all,rt[maxn];
struct tree{
count l,r;
count ls,rs;
value sum;
value cnt;
} shu[maxn<<5];
inline void copy(count &hao){
shu[++all]=shu[hao];
hao=all;
}
inline void pushup(count hao){
shu[hao].cnt=(shu[shu[hao].ls].cnt+shu[shu[hao].rs].cnt);
shu[hao].sum=(shu[shu[hao].ls].sum+shu[shu[hao].rs].sum);
// debug(shu[hao].sum)
}
void insert(count &hao,count l,count r,count pos){
copy(hao);
shu[hao].l=l,shu[hao].r=r;
if(l==r){
shu[hao].cnt++;
shu[hao].sum+=book[pos];
return ;
}
count mid=(l+r)>>1;
if(pos<=mid) insert(shu[hao].ls,l,mid,pos);
else insert(shu[hao].rs,mid+1,r,pos);
pushup(hao);
}
value askda(count hao,count l,count r,count jian){
if(!hao) return 0;
if(l<=shu[hao].l && r>=shu[hao].r){
// debug('$'<<shu[hao].cnt<<' '<<shu[hao].sum<<' '<<jian)
value val=std::max(0ll,shu[hao].sum-shu[hao].cnt*jian);
return val;
}
count mid=(shu[hao].l+shu[hao].r)>>1;
value val=0;
if(l<=mid) val+=askda(shu[hao].ls,l,r,jian);
if(r>mid) val+=askda(shu[hao].rs,l,r,jian);
return val;
}
value askx(count hao,count l,count r,count jian){
if(!hao) return 0;
if(l<=shu[hao].l && r>=shu[hao].r){
// debug('&'<<shu[hao].cnt<<' '<<shu[hao].sum<<' '<<jian)
return std::max(0ll,shu[hao].cnt*jian-shu[hao].sum);
}
count mid=(shu[hao].l+shu[hao].r)>>1;
value val=0;
if(l<=mid) val+=askx(shu[hao].ls,l,r,jian);
if(r>mid) val+=askx(shu[hao].rs,l,r,jian);
return val;
}
inline value f(value i,value ll){
value da=b*std::max(0ll,askda(rt[i],ll+1,m,book[ll]));
value xiao=a*std::max(0ll,askx(rt[i],1,ll-1,book[ll]));
// debug(da<<' '<<xiao<<' '<<da+xiao)
return da+xiao? da+xiao:1;
// return ask(rt[i],1,m,book[ll]);
}
int main(){
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
n=read(),a=read(),b=read();
for(count i=1;i<=n;i++){
x[i]=read();
book[i]=x[i];
// debug(x[i])
}
std::sort(book+1,book+1+n);
m=std::unique(book+1,book+1+n)-book-1;
for(count i=1;i<=n;i++){
zhen[i]=std::lower_bound(book+1,book+1+m,x[i])-book;
// debug(zhen)
rt[i]=rt[i-1];
insert(rt[i],1,book[m],zhen[i]);
}
// debug(asksum(rt[n],1,n))
// debug("OK")
write(0),putchar('\n');
count pre=1;
for(count i=2;i<=n;i++){
count l=pre,r=zhen[i];
if(l>r) std::swap(l,r);
value ans=1ll << 60;
while(l+10<r){
value ll=l+4*(r-l)/9;
value rr=r-4*(r-l)/9;
value lm=f(i,ll);
value rm=f(i,rr);
if(lm<rm){
r=rr;
}
else{
l=ll;
}
}
for(count j=l;j<=r;j++){
if(f(i,j)<ans){
ans=f(i,j);
pre=j;
}
}
write(ans),putchar('\n');
}
return 0;
}
/*
5 3 2
5 1 4 2 3
*/
T4 金牌
赛时没时间打完力（悲）
对于询问的两个点不是互为祖孙的情况，\(ans=\sum_{i\in subtree_x} \sum_{j\in subtree_y} 2^{dis_{x,y}+dis_{i,x}+dis_{j,y}}\)
利用什么因式分解能 \(ans=(\sum 2^{dis_{i,x}})\times (\sum 2^{dis{j,y}})\times 2^{dis_{x,y}}\)
这个可以dfs一遍直接求出每棵子树的贡献之和，求 lca 算第三项。
对于一点为另一点祖先的情况，设 \(x\) 为祖先。换个根，把 \(x,y\) 中间某个点看作根，这个形状好像和前面的式子适用的情况一样。发现原本式子里面的 \(\sum 2^{dis_{i,x}}\) 就是全局经过 \(x\) 的路径的贡献减去 \(x\) 的儿子里包含 \(y\) 的子树的贡献，然后代刚才的式子就好。
有个树链剖分求祖先直接儿子的技巧，就是往上跳，如果当前在轻链上必定有个时候是当前点 \(top\) 的爹是祖先，直接返回 \(top\)；如果在重链上（就是上面没跳到）就直接从祖先的位置的 \(dfn\) +1，然后找当前 \(dfn\) 对应的点。
点击查看代码
#include<bits/stdc++.h>
typedef int count ;
typedef long long value;
inline value read(){
count f(1);
value x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
void write(value x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
#define debug(x) std::cerr<<"###"<<x<<std::endl;
#define mod 998244353
#define maxn 1000010
count n,q;
count head[maxn],tot;
struct bian{
count to,nx;
} bian[maxn<<1];
inline void add(count from,count to){
bian[++tot].to=to;
bian[tot].nx=head[from];
head[from]=tot;
}
count num,in[maxn],out[maxn];
count dep[maxn],top[maxn],f[maxn],son[maxn],size[maxn];
value dp[maxn],wai[maxn];
void dfs1(count x,count fa){
dep[x]=dep[fa]+1;
size[x]=1;
dp[x]=1;
for(count i=head[x];i;i=bian[i].nx){
count y=bian[i].to;
if(y==fa) continue;
f[y]=x;
dfs1(y,x);
size[x]+=size[y];
if(size[y]>size[son[x]]){
son[x]=y;
}
dp[x]=(dp[x]+dp[y]*2ll%mod)%mod;
}
out[x]=num;
}
count duiy[maxn];
void dfs2(count x,count topf){
top[x]=topf;
in[x]=++num;
duiy[num]=x;
wai[x]=dp[x];
if(!son[x]) return ;
value cunx=dp[x],cuny=dp[son[x]];
dp[x]=((dp[x]-2ll*dp[son[x]]%mod)+mod)%mod;
dp[son[x]]=(dp[son[x]]+2ll*dp[x]%mod)%mod;
dfs2(son[x],topf);
dp[x]=cunx;
dp[son[x]]=cuny;
for(count i=head[x];i;i=bian[i].nx){
count y=bian[i].to;
if(y==f[x] || y==son[x]) continue;
value cunx=dp[x],cuny=dp[y];
dp[x]=(dp[x]-2ll*dp[y]%mod+mod)%mod;
dp[y]=(dp[y]+2ll*dp[x]%mod+mod)%mod;
dfs2(y,y);
dp[x]=cunx;
dp[y]=cuny;
}
out[x]=num;
}
inline count lca(count x,count y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) std::swap(x,y);
x=f[top[x]];
}
if(dep[x]>dep[y]) std::swap(x,y);
return x;
}
inline count xia(count x,count y){
while(top[x]!=top[y]){
if(f[top[x]]==y) return top[x];
x=f[top[x]];
}
return duiy[in[y]+1];
}
inline value kuai(value base,count x){
value val=1;
while(x){
if(x&1) val=val*base%mod;
base=base*base%mod;
x>>=1;
}
return val;
}
value base[maxn];
int main(){
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
n=read();
for(count i=1;i<=n-1;i++){
count b=read(),c=read();
add(b,c);
add(c,b);
}
base[0]=1;
for(count i=1;i<=n;i++){
base[i]=base[i-1]*2ll%mod;
// debug(base[i])
}
dfs1(1,0);
dfs2(1,1);
q=read();
while(q--){
count x=read(),y=read();
count an=lca(x,y);
// debug(an)
if(in[x]>in[y]) std::swap(x,y);
if(in[y]<=out[x]){
count sec=xia(y,x);
// debug(sec)
count dis=dep[y]-dep[x];
value sum=(wai[x]-2ll*dp[sec]%mod+mod)%mod;
value ans=1;
ans=(ans*base[dis]%mod*dp[y]%mod*sum)%mod;
write(ans),putchar('\n');
}else{
value dis=dep[x]+dep[y]-(dep[an]<<1);
value ans=base[dis]%mod;
ans=(ans*dp[x]%mod*dp[y])%mod;
write(ans),putchar('\n');
}
}
return 0;
}