【Codeforces】1109 Round #539 (Div. 1)B-F题解

传送门:CF1109

B.Sasha and One More Name

首先判断全部相同或是奇回文且只有$mid$不同的情况，无解。

如果是奇回文，至少都要切$2$刀，且下界一定能达到。
如果是偶回文，不断把字符串长度$/2$(砍一半)，直到出现奇回文或不回文子串：
若出现奇回文，还是至少切$2$刀的情况，且下界一定能达到。
否则只用切一刀。

#include
#define fl() puts("Impossible"),exit(0)
using namespace std;
const int N=5003;int n;
char s[N];int main(){int i,j,mid;scanf("%s",s+1);n=strlen(s+1);mid=n>>1;for(i=2;i<=mid && (s[i]==s[i-1]);++i);if(i>mid) fl();if(n&1) puts("2");else{for(;;mid>>=1){for(i=1;mid-i+1>i && (s[i]==s[mid-i+1]);++i);if((mid-i+1<=i) && (mid&1)) {puts("2");break;}else if(mid-i+1>i){puts("1");break;}}}return 0;}

C.Sasha and a Patient Friend

大概可以把$l,r$离散化之后套个$set+线段树$。
然而直接$BST$维护每次查询二分。

代码咕咕咕。

D.Sasha and Interesting Fact from Graph Theory

枚举$a,b$链上的点数$k(0\le k\le n-2)$：

选出$k$个点的方案 ( n − 2 ) ! ( n − 2 − k ) ! \dfrac{(n-2)!}{(n-2-k)!} (n−2−k)!(n−2)!​，链上$k+1$条边边权方案 ( m − 1 k ) \dbinom{m-1}{k} (km−1​)，剩下$n-k-2$条边边权的方案 m n − k − 2 m^{n-k-2} mn−k−2。

关于怎么统计把剩下$n-2-k$任意连向这条链的方案数，存在$\text{Cayley’s formula}$：
f ( n , k ) = k ⋅ n n − k − 1 f(n,k)=k·n^{n-k-1} f(n,k)=k⋅nn−k−1

即$n$个点的森林$k$个连通块，且$1,2,...,k$在不同连通块中的方案数。
数学归纳法证明-ymz

a n s = ∑ k = 0 n − 2 ( n − 2 ) ! ( n − 2 − k ) ! ( m − 1 k ) m n − k − 2 f ( n , k + 2 ) ( m o d 1 0 9 + 7 ) ans=\sum \limits_{k=0}^{n-2}\dfrac{(n-2)!}{(n-2-k)!}\dbinom{m-1}{k}m^{n-k-2}f(n,k+2) \pmod {10^9+7} ans=k=0∑n−2​(n−2−k)!(n−2)!​(km−1​)mn−k−2f(n,k+2)(mod109+7)

E. Sasha and a Very Easy Test

$mod$最多只有$9$个不同的质因子，设$mod$质因子集合为$p$

考虑构造两个线段树，第一颗维护原值，第二颗维护 a i a_i ai​去掉所有$p$中因子的值 b i b_i bi​，且 a i a_i ai​中 p j p_j pj​的次幂为 w a i j w_{a_ij} wai​j​。乘法直接做即可，注意$|p|$颗$BIT$分别维护每个位置上 p i p_i pi​加上的次幂。

对于单点除以$x$，设$x$去掉所有$p$中因子后值为 x ′ x' x′，且$x$中 p i p_i pi​的次幂为 w i w_{i} wi​：
a i x ≡ b i x ′ ∏ k = 1 ∣ p ∣ p i a i k − w k ( m o d m o d ) \dfrac{a_i}{x}\equiv \dfrac{b_i}{x'}\prod\limits_{k=1}^{|p|}p_i^{a_{ik}-w_k}\pmod {mod} xai​​≡x′bi​​k=1∏∣p∣​piaik​−wk​​(modmod)

x ′ ’ x'’ x′’可以直接求逆元，其它在$BIT$中查一下也可以算出来。

贴了yyb大佬的代码:

#include
#include
using namespace std;
#define MAX 100100
#define lson (now<<1)
#define rson (now<<1|1)
inline int read()
{int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x;
}
int fpow(int a,int b,int MOD){int s=1;while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}return s;}
void exgcd(int a,int b,int &x,int &y){if(!b){x=1;y=0;return;}exgcd(b,a%b,y,x);y-=a/b*x;}
int Inv(int a,int MOD){int x,y;exgcd(a,MOD,x,y);x=(x%MOD+MOD)%MOD;return x;}
int n,MOD,Q,a[MAX],fac[10],tot;
int p[10][MAX];
struct SegMentTree
{int t[MAX<<2],tag[MAX<<2];void Build(int now,int l,int r){tag[now]=1;if(l==r){t[now]=a[l]%MOD;return;}int mid=(l+r)>>1;Build(lson,l,mid);Build(rson,mid+1,r);t[now]=(t[lson]+t[rson])%MOD;}void puttag(int now,int w){t[now]=1ll*t[now]*w%MOD;tag[now]=1ll*tag[now]*w%MOD;}void pushdown(int now){if(tag[now]==1)return;puttag(lson,tag[now]);puttag(rson,tag[now]);tag[now]=1;}void Modify(int now,int l,int r,int p,int w){if(l==r){t[now]=w;return;}int mid=(l+r)>>1;pushdown(now);if(p<=mid)Modify(lson,l,mid,p,w);else Modify(rson,mid+1,r,p,w);t[now]=(t[lson]+t[rson])%MOD;}void Modify_mul(int now,int l,int r,int L,int R,int w){if(L<=l&&r<=R){puttag(now,w);return;}int mid=(l+r)>>1;pushdown(now);if(L<=mid)Modify_mul(lson,l,mid,L,R,w);if(R>mid)Modify_mul(rson,mid+1,r,L,R,w);t[now]=(t[lson]+t[rson])%MOD;}int Query(int now,int l,int r,int L,int R){if(L<=l&&r<=R)return t[now];int mid=(l+r)>>1,ret=0;pushdown(now);if(L<=mid)ret=(ret+Query(lson,l,mid,L,R))%MOD;if(R>mid)ret=(ret+Query(rson,mid+1,r,L,R))%MOD;return ret;}
}T1,T2;
int lb(int x){return x&(-x);}
struct BIT
{int c[MAX];void add(int x,int w){while(x<=n)c[x]+=w,x+=lb(x);}int getsum(int x){int s=0;while(x)s+=c[x],x-=lb(x);return s;}void Modify(int l,int r,int w){add(l,w);add(r+1,-w);}
}T[10];
int Div[10];
int Fact(int x)
{for(int i=1;i<=tot;++i)Div[i]=0;for(int i=1;i<=tot;++i)while(x%fac[i]==0)Div[i]+=1,x/=fac[i];return x;
}
int main()
{n=read();MOD=read();for(int i=1;i<=n;++i)a[i]=read();int P=MOD;for(int i=2;i*i<=MOD;++i)if(P%i==0){fac[++tot]=i;while(P%i==0)P/=i;}if(P>1)fac[++tot]=P;T1.Build(1,1,n);for(int i=1;i<=n;++i)for(int j=1;j<=tot;++j)while(a[i]%fac[j]==0)++p[j][i],a[i]/=fac[j];T2.Build(1,1,n);Q=read();while(Q--){int opt=read();if(opt==1){int l=read(),r=read(),x=read();T2.Modify_mul(1,1,n,l,r,Fact(x)%MOD);for(int i=1;i<=tot;++i)T[i].Modify(l,r,Div[i]);T1.Modify_mul(1,1,n,l,r,x%MOD);}else if(opt==2){int l=read(),x=read(),c=Fact(x);for(int i=1;i<=tot;++i)p[i][l]-=Div[i];for(int i=1;i<=tot;++i)Div[i]=p[i][l]+T[i].getsum(l);c=1ll*T2.Query(1,1,n,l,l)*Inv(c,MOD)%MOD;T2.Modify(1,1,n,l,c);for(int i=1;i<=tot;++i)c=1ll*c*fpow(fac[i],Div[i],MOD)%MOD;T1.Modify(1,1,n,l,c);}else{int l=read(),r=read();printf("%d\n",T1.Query(1,1,n,l,r));}}return 0;
}

F.Sasha and Algorithm of Silence’s Sounds

格子连通性是比较明显的暗示了$LCT$？

从小到大枚举右端点$r$：
$LCT$处理出 L r L_r Lr​表示最小的满足 [ L r , r ] [L_r,r] [Lr​,r]构成森林。
求出 L r ≤ l ≤ r L_r\leq l\leq r Lr​≤l≤r中满足$[l,r]$为树的个数，考虑线段树维护：
森林连通块个数=点数-边数，线段树维护每个下标$[i,r]$森林连通块个数 q i q_i qi​。
q i ≥ 1 q_i\geq 1 qi​≥1，只需要保证区间最小值为$1$，维护最小值的个数即可。

再贴yyb的代码(雾

#include
#include
using namespace std;
#define ll long long
#define ls (t[x].ch[0])
#define rs (t[x].ch[1])
inline int read()
{int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x;
}
struct Node{int ff,ch[2],rev;}t[200200];
bool isroot(int x){return t[t[x].ff].ch[0]!=x&&t[t[x].ff].ch[1]!=x;}
void rotate(int x)
{int y=t[x].ff,z=t[y].ff;int k=t[y].ch[1]==x;if(!isroot(y))t[z].ch[t[z].ch[1]==y]=x;t[x].ff=z;t[y].ch[k]=t[x].ch[k^1];t[t[x].ch[k^1]].ff=y;t[x].ch[k^1]=y;t[y].ff=x;
}
void pushdown(int x){if(t[x].rev)t[ls].rev^=1,t[rs].rev^=1,swap(ls,rs),t[x].rev^=1;}
int S[200200],top;
void Splay(int x)
{S[top=1]=x;for(int i=x;!isroot(i);i=t[i].ff)S[++top]=t[i].ff;while(top)pushdown(S[top--]);while(!isroot(x)){int y=t[x].ff,z=t[y].ff;if(!isroot(y))(t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);rotate(x);}
}
void access(int x){for(int y=0;x;y=x,x=t[x].ff)Splay(x),rs=y;}
void makeroot(int x){access(x);Splay(x);t[x].rev^=1;}
void split(int x,int y){makeroot(x);access(y);Splay(y);}
void link(int x,int y){makeroot(x);t[x].ff=y;}
void cut(int x,int y){split(x,y);t[y].ch[0]=t[x].ff=0;}
int findroot(int x){access(x);Splay(x);while(ls)x=ls;return x;}
int n,m;ll ans;
int a[1010][1010];
int X[200200],Y[200200];
int d[4][2]={1,0,0,1,-1,0,0,-1};
struct SegMent
{
#define lson (now<<1)
#define rson (now<<1|1)struct Node{int v,s;}t[200200<<2];int tag[200200<<2];Node Merge(Node a,Node b){Node c;c.v=min(a.v,b.v);c.s=0;if(c.v==a.v)c.s+=a.s;if(c.v==b.v)c.s+=b.s;return c;}void pushup(int now){t[now]=Merge(t[lson],t[rson]);}void Build(int now,int l,int r){if(l==r){t[now]=(Node){1,1};return;}int mid=(l+r)>>1;Build(lson,l,mid);Build(rson,mid+1,r);pushup(now);}void puttag(int now,int w){t[now].v+=w;tag[now]+=w;}void pushdown(int now){puttag(lson,tag[now]);puttag(rson,tag[now]);tag[now]=0;}void Modify(int now,int l,int r,int L,int R,int w){if(L<=l&&r<=R){puttag(now,w);return;}int mid=(l+r)>>1;pushdown(now);if(L<=mid)Modify(lson,l,mid,L,R,w);if(R>mid)Modify(rson,mid+1,r,L,R,w);pushup(now);}Node Query(int now,int l,int r,int L,int R){if(L==l&&r==R)return t[now];int mid=(l+r)>>1;pushdown(now);if(R<=mid)return Query(lson,l,mid,L,R);if(L>mid)return Query(rson,mid+1,r,L,R);return Merge(Query(lson,l,mid,L,mid),Query(rson,mid+1,r,mid+1,R));}int Query(int l,int r){Node a=Query(1,1,n*m,l,r);return a.v==1?a.s:0;}
}T;
bool check(int l,int r,int p)
{for(int i=0;i<4;++i){int x=X[p]+d[i][0],y=Y[p]+d[i][1];if(x<0||y<0||x>n||y>m)continue;if(!(l<=a[x][y]&&a[x][y]<=r))continue;for(int j=i+1;j<4;++j){int xx=X[p]+d[j][0],yy=Y[p]+d[j][1];if(xx<0||yy<0||xx>n||yy>m)continue;if(!(l<=a[xx][yy]&&a[xx][yy]<=r))continue;if(findroot(a[x][y])==findroot(a[xx][yy]))return false;}}return true;
}
void Work(int l,int r,int p,int opt)
{for(int i=0;i<4;++i){int x=X[p]+d[i][0],y=Y[p]+d[i][1];if(x<0||y<0||x>n||y>m)continue;if(!(l<=a[x][y]&&a[x][y]<=r))continue;if(opt==-1)cut(p,a[x][y]);else link(p,a[x][y]),T.Modify(1,1,n*m,1,a[x][y],-1);}
}
int main()
{n=read();m=read();T.Build(1,1,n*m);for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)a[i][j]=read();for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)X[a[i][j]]=i,Y[a[i][j]]=j;for(int i=1,p=1;i<=n*m;++i){while(!check(p,i-1,i))Work(p+1,i-1,p,-1),++p;Work(p,i-1,i,1);ans+=T.Query(p,i);T.Modify(1,1,n*m,p,i,1);}printf("%I64d\n",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！