A
注意到答案一定是 最小公倍数的倍数，
最大公因数的因数，特判特殊情况即可。
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d;long long gcd,lcm;
inline int Gcd(int x,int y) {return y?Gcd(y,x%y):x;}
bool Find(int x) {for(int i=2; i*i<=x; ++i)if(x%i==0)return cout<<lcm*i,true;return false;}
int main() {
cin>>a>>b>>c>>d,gcd=Gcd(b,d),lcm=1ll*a*c/Gcd(a,c);
if(gcd%lcm!=0)puts("-1");
else if(gcd<min(b,d)&&gcd>max(a,c))cout<<gcd;
else if(lcm<min(b,d)&&lcm>max(a,c))cout<<lcm;
else if(!Find(gcd/lcm))puts("-1");
return 0;
}B
一道较易的图论题目。
我们考虑贪心，显然我们会先把一个已经连通的块先连成一个完全图，这样是不会减少连通块个数的，然后我们考虑对连通块进行连边。
注意到一个显然的贪心就是我们一定会先将两个 大的连通块连成一个连通块，因为这样连出去的边更多，那么我们考虑将排序后的前
个连通块合并，这样所能添加的总边数为
对于询问离线，我们用双指针同时遍历询问和连通块，更新答案，时间复杂度 ，为排序的复杂度。
值得一提的是，这道题出题人原本想加上加边操作，然后强制在线的，但考虑到这样做后就必须使用高级数据结构动态维护 ，违背了出这道 T2 的初心（初心当然是送分啊），于是就去掉了加边操作。
#include<bits/stdc++.h>
#define N 500005
#define ll long long
using namespace std;
int n,m,Q,prt[N],siz[N];
int num,bl[N],ans[N];
ll fir;
struct query {
int id;
ll x;
bool operator<(query a) const {
return x<a.x;
}
} q[N];
inline ll read() {
ll s=0;
char ch=getchar();
while(ch<48||ch>57)ch=getchar();
while(ch>47&&ch<58)s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
int Getprt(int x) {
return x==prt[x]?x:prt[x]=Getprt(prt[x]);
}
signed main() {
n=read(),m=read(),Q=read();
for(int i=1; i<=n; ++i)prt[i]=i;
for(int i=1; i<=m; ++i)prt[Getprt(read())]=Getprt(read());
for(int i=1; i<=n; ++i)if(i==Getprt(i))bl[i]=++num;
for(int i=1; i<=n; ++i)++siz[bl[i]=bl[Getprt(i)]];
for(int i=1; i<=num; ++i)fir+=siz[i]*(siz[i]-1ll)>>1;
for(int i=1; i<=Q; ++i)q[i].x=read(),q[i].id=i;
fir-=m,sort(siz+1,siz+num+1),sort(q+1,q+Q+1);
for(int i=1,j=num; i<=Q; ++i) {
while(q[i].x>fir) {
fir-=(siz[j]*(siz[j]-1ll)>>1)+(siz[j-1]*(siz[j-1]-1ll)>>1);
siz[j-1]+=siz[j],--j,fir+=siz[j]*(siz[j]-1ll)>>1;
}
ans[q[i].id]=j;
}
for(int i=1; i<=Q; ++i)cout<<ans[i]<<"\n";
return 0;
}C
注意到一个回文数会由前 位确定，所以我们考虑用这个性质来解题。
因为 有
，所以不能
枚举，而只能采取复杂度更低的算法，比较容易想到的是二分。
我们考虑求出 的数的个数，这个可以用O(位数)的复杂度快速求出。
然后我们二分答案 判断即可，复杂度
，这里本来可以将
开到
，但高精度过于毒瘤，出题人不想写就咕掉了，同时，复杂度应该也可以做到
，但实现过于毒瘤，建议不要尝试。
#include<bits/stdc++.h>
using namespace std;
long long x,k,y,cx,a[25];
long long G[]= {0,9,18,108,198,1098,1998,10998,19998,109998,199998,1099998,1999998,10999998,19999998,109999998,199999998,1099999998,1999999998};
long long Rev(long long n) {
long long ans=0;
while(n)ans=(ans*10+n%10),n/=10;
return ans;
}
long long Get(long long n) {
long long nn=n,ans=0,kk=1,cnt=0,bb=0;
while(nn)a[++cnt]=nn%10,nn/=10;
ans+=G[cnt-1],nn=n;
for(int i=1; i<=(cnt>>1); ++i)nn/=10;
for(int i=1; i<(cnt+1>>1); ++i)kk*=10;
ans+=nn-kk,bb=nn,nn=0;
if(cnt&1)bb/=10;
for(int i=(cnt>>1); i; --i)nn=(nn*10+a[i]);
return ans+(Rev(bb)<=nn);
}
signed main() {
cin>>x>>k;
long long l=0,r=5e17,mid,ans;
cx=Get(x-1);
while(l<=r) {
if(Get(mid=(l+r)>>1)-cx>=k)r=mid-1;
else l=mid+1,ans=mid;
}
cout<<ans+1;
return 0;
}D
一道较为模板的字符串+矩阵快速幂。
首先注意到期望就是 总匹配数/总方案，后者很好求，只需求前者。
前者我们先考虑一个暴力DP，设 为前
个字符，能够匹配到KMP自动机上的第
个字符的总匹配串数，那么转移就很显然：
，所以根据这个递推式我们构造矩阵进行快速幂。
设一个 维向量
分别表前
个字符匹配到自动机上的第
个节点的方案数，
到目前的答案和。
然后构造转移矩阵 矩阵快速幂进行转移即可。
至于每一个限制，做分层的矩阵快速幂即可，注意很多边界的判断。
#include<bits/stdc++.h>
#define N 105
using namespace std;
const int mod=998244353;
int n,m,k,ck[27],ch[N][27],fail[N],pw[N],num,AA;
char s[N],cc;
struct query {
int x,opt,ch;
bool operator<(query a) const {
return x<a.x||(x==a.x&&opt<a.opt);
}
} q[505];
struct Matrix {
int n,m,c[N][N];
Matrix(int _n=0,int _m=0) {
n=_n,m=_m;
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)c[i][j]=0;
}
Matrix operator*(Matrix a) const {
Matrix ans(n,a.m);
for(int i=0; i<n; ++i)for(int j=0; j<m; ++j)if(c[i][j])
for(int k=0; k<a.m; ++k)ans.c[i][k]=(ans.c[i][k]+1ll*c[i][j]*a.c[j][k])%mod;
return ans;
}
} arr[32],Arr,ans;
int Ksm(int a,int n,int ans=1) {
for(; n; n>>=1,a=1ll*a*a%mod)if(n&1)ans=1ll*ans*a%mod;
return ans;
}
char nc(char ch=getchar()) {
while(ch<'a'||ch>'z')ch=getchar();
return ch;
}
void Mul(Matrix &ans,int m) {
for(int i=0; i<=30; ++i)if(m>>i&1)ans=ans*arr[i],num=1ll*num*pw[i]%mod;
}
int main() {
scanf("%d%d%d%s",&n,&m,&k,s+1),ch[0][s[1]-'a']=num=1,ch[1][s[2]-'a']=2;
for(int i=2,j=0; i<=n; ++i) {
while(j&&s[j+1]!=s[i])j=fail[j];
fail[i]=j=(s[j+1]==s[i]?j+1:j);
if(i<n)ch[i][s[i+1]-'a']=i+1;
}
arr[0]=Matrix(n+2,n+2),arr[0].c[n+1][n+1]=pw[0]=26;
for(int i=0; i<=n; ++i)
for(int j=0; j<26; ++j) {
if(!ch[i][j])ch[i][j]=ch[fail[i]][j];
++arr[0].c[i][ch[i][j]];
}
for(int i=0; i<=n; ++i)arr[0].c[i][n+1]=arr[0].c[i][n];
for(int i=1; i<=30; ++i)arr[i]=arr[i-1]*arr[i-1],pw[i]=1ll*pw[i-1]*pw[i-1]%mod;
ans=Matrix(1,n+2),ans.c[0][0]=1;
for(int i=1; i<=k; ++i)cin>>q[i].opt>>q[i].x>>cc,q[i].ch=cc;
sort(q+1,q+k+1);
for(int i=1,j=1,las=0; i<=k; i=j) {
Mul(ans,q[i].x-las-1),Arr=Matrix(n+2,n+2);
Arr.c[n+1][n+1]=AA=0;
while(q[j].x==q[i].x)++j;
for(int l=0; l<26; ++l)ck[l]=1;
for(int l=i; l<j; ++l) {
if(!q[l].opt)ck[q[l].ch-'a']=0;
else for(int ii=0; ii<26; ++ii)if(q[l].ch-'a'!=ii)ck[ii]=0;
}
for(int jj=0; jj<26; ++jj)if(ck[jj])++Arr.c[n+1][n+1],++AA;
for(int ii=0; ii<=n; ++ii)
for(int jj=0; jj<26; ++jj)if(ck[jj]) {
if(!ch[ii][jj])ch[ii][jj]=ch[fail[ii]][jj];
++Arr.c[ii][ch[ii][jj]];
}
for(int ii=0; ii<=n; ++ii)Arr.c[ii][n+1]=Arr.c[ii][n];
ans=ans*Arr,las=q[i].x,num=1ll*num*AA%mod;
}
if(m!=q[k].x)Mul(ans,m-q[k].x);
cout<<1ll*ans.c[0][n+1]*Ksm(num,mod-2)%mod<<"\n";
return 0;
}E
我们考虑使用欧拉反演。
因为有：
$$
同理可得：
其中 表示
的最小公倍数。
转换成这样之后，我们就只需仿照 旧试题的做法，可以对每个
的点对之间连一条边，然后跑三元环计数，贡献可以在枚举每个三元环的时候算，复杂度是
的，其中
是图的总边数，总数较小，当
时
，实测本地需要
，牛客网需要
。
考虑怎样找 的点对，直接枚举最大公因数
，枚举
都为
的倍数且
，然后当
时我们就连
这条边，复杂度应为
。
#include<bits/stdc++.h>
#define N 100005
#define ll long long
using namespace std;
const int mod=998244353;
int n,m,r,p[N],cnt,ey[N*100],vv[N];
int d[N],vis[N],ex[N*100];
ll phi[N],ans;
vector<int>g[N],h[N];
map<int,int>mp[N];
void Addedge(int x,int y) {
g[x].push_back(y),++d[x];
g[y].push_back(x),++d[y];
}
void Pre(int n) {
phi[1]=1;
for(int i=2; i<=n; ++i) {
if(!vis[i])vis[i]=p[++cnt]=i,phi[i]=i-1;
for(int j=1; i*p[j]<=n&&j<=cnt; ++j) {
if(vis[i*p[j]]=p[j],i%p[j]==0) {
phi[i*p[j]]=phi[i]*p[j];
break;
}
phi[i*p[j]]=phi[i]*(p[j]-1);
}
}
}
int Gcd(int x,int y) {
return y?Gcd(y,x%y):x;
}
ll Lcm(ll x,ll y) {
return x/Gcd(x,y)*y;
}
ll Bao(int n,int m,int r,ll ans=0) {
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
for(int k=1; k<=r; ++k)ans=(ans+1ll*Gcd(i,j)*Gcd(j,k)*Gcd(i,k))%mod;
return ans;
}
int main() {
cin>>n,Pre(100000),cnt=0;
for(ll i=1; i<=n; ++i)vis[i]=0,ans=(ans+phi[i]*phi[i]*phi[i]*(n/i)*(n/i)*(n/i))%mod;
for(ll i=1; i<=n; ++i)for(ll j=1; i*j<=n; ++j)for(ll k=j+1; i*j*k<=n; ++k)if(Gcd(j,k)==1)++d[ex[++cnt]=i*j],++d[ey[cnt]=i*k];
for(int i=1; i<=cnt; ++i) {
int x=ex[i],y=ey[i];
if(d[x]<d[y])swap(x,y);
ans=(ans+3*phi[x]*phi[x]*phi[y]*(n/x)*(n/Lcm(x,y))*(n/Lcm(x,y)))%mod;
ans=(ans+3*phi[y]*phi[y]*phi[x]*(n/y)*(n/Lcm(x,y))*(n/Lcm(x,y)))%mod;
g[x].push_back(y);
}
for(int i=1; i<=n; ++i) {
h[i].resize(g[i].size());
for(int j=0; j<g[i].size(); ++j)h[i][j]=n/Lcm(i,g[i][j]);
}
for(int i=1; i<=n; ++i) {
for(int j:g[i])vis[j]=i,vv[j]=n/Lcm(i,j);
for(int j:g[i]) {
for(int z=0,k; z<g[j].size(); ++z)
if(vis[k=g[j][z]]==i)ans=(ans+6*phi[i]*phi[j]*phi[k]*vv[j]*vv[k]*h[j][z])%mod;
}
}
cout<<ans<<"\n";
return 0;
}F
前置知识：prufer序列
prufer序列告诉我们： 个点有标号有根树的数量是
，并且这些树与长度为
，值域为
的数列一一对应。具体如何一一对应建议看模板题。
本题题解
这道题是求所有点深度的 m 次方之和，那么我们可以枚举一条长度为 的到根链，考虑剩下的
个点如何统计。
我们可以考虑把这些树与 prufer 序列之间建立一一对应的关系，钦定标号最大的 个点就是我们选的这
个点，并且自底向上标号为
（这里的钦定只是为了统计合法方案，并不是真的就是标号最大的
个点），然后考虑对这棵树做 prufer 序列，那么 prufer 序列上最后的
个点一定是这条链上的点，并且标号一定是从
，最后剩下
和
，并且 prufer 序列的前
个值是任意选的，只有第
个值必须在
之间，所以其它点的 prufer 序列的方案数是
。
由于 prufer 序列和树是一一对应的，我们得到在固定一条长度为 的点之后，剩下的点的有标号生成树（接在这条链下方）数量为
，我们只需乘上标号分配方案
就是钦定一条长度为
链的有标号有根树数目，然后乘上贡献
再求和就是答案。
故最后表达式为：
只需线性筛 复杂度就可做到
的复杂度。
#include<bits/stdc++.h>
#define N 10000005
using namespace std;
const int mod=421969921;
long long m;
int n,S,invn,fac[N],inv[N];
int ans,p[N],cnt,vis[N],F[N];
inline int Ksm(int a,long long n,int ans=1) {for(; n; n>>=1,a=1ll*a*a%mod)if(n&1)ans=1ll*ans*a%mod;return ans;}
void Pre() {
for(int i=fac[0]=1; i<=n; ++i)fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=Ksm(fac[n],mod-2);for(int i=n-1; ~i; --i)inv[i]=inv[i+1]*(i+1ll)%mod;F[1]=1;
for(int i=2; i<=n; ++i) {
if(!vis[i])p[++cnt]=i,F[i]=Ksm(i,m+1);
for(int j=1; j<=cnt&&i*p[j]<=n; ++j) {
vis[i*p[j]]=1,F[i*p[j]]=1ll*F[i]*F[p[j]]%mod;
if(i%p[j]==0)break;
}
}
}
int main() {
cin>>n>>m;if(n==1)return puts("1"),0;Pre(),invn=Ksm(n,mod-2),S=Ksm(n,n-2);
for(int i=1; i<=n; ++i)ans=(ans+1ll*F[i]*S%mod*fac[n]%mod*inv[n-i])%mod,S=1ll*S*invn%mod;cout<<ans;
return 0;
}G
假设只考虑操作1，考虑两个区间,
且
和
有相邻元素，和一个线段树维护区间
：
，那么显然这个节点以下是不会出现
的节点的。那么
无关。
，那么对
的操作修改一定不会在这个节点终止。那么我们可以认为
对
有了以上两条性质，那么一个线段树节点的加标记修改，就可以一一对应一个操作1的修改。这个区间需要满足包含这个线段树区间，且不存在比它短的区间包含这个线段树区间。我们可以通过对线段树边标记的方法来确定一对父子节点的和标记修改是否对应同一个标号区间，线段树点开一个表示修改这个线段树节点对应修改标号区间的点的个数，可以完成操作1，贡献就是
。
考虑操作2，与操作1搞好相反，他们的区间取交为空，取并为全集。直接取反即可。
考虑标记下放，容易发现，操作1的标记只会作用于父子节点的对应修改标号区间相同的节点，操作2的修改全部下放，特判增加一个操作1标记。
考虑在消去标号区间的时候，我们首先会递归到这些点，所以他们到根的路径是没有标记的，然后我们需要判断他是否会合并到父亲，这里开一个维护左端点，每次判断即可。
为了卡掉并查集做法，我们加大数据范围，强制在线，让它不能缩点。线段树动态开点即可。
然后可以把优化为直接维护元素个数优化到严格
。这里出题人给了
过的。
#include<bits/stdc++.h>
using namespace std;
long long p1=1000000,p2=0;
char buf[1000005],wb[1000005];
long long gc() {
if(p1>=1000000)fread(buf,1,1000000,stdin),p1=0;
return buf[p1++];
}
#define gc getchar
long long getint() {
long long ret=0,flag=1;
char c=gc();
while(c<'0'||c>'9') {
if(c=='-')flag=-1;
c=gc();
}
while(c<='9'&&c>='0') {
ret=(ret<<3)+(ret<<1)+c-'0';
c=gc();
}
return ret*flag;
}
void pc(char x) {
if(p2>=1000000)fwrite(wb,1,1000000,stdout),p2=0;
wb[p2++]=x;
}
void wrt(long long x) {
if(x<0)pc('-'),x=-x;
long long c[24]= {0};
if(!x)return pc('0'),void();
while(x)c[++c[0]]=x%10,x/=10;
while(c[0])pc(c[c[0]--]+'0');
}
#define mod 998244353
int n,m,Q,root;
int rd[200005],cd[200005];
struct Segment_tree {
int tot;
struct node {
int prt,ls,rs;
bool lc,rc;
long long len,lenc;
long long stag,stagc;
long long sum;
set<int> s;
} v[3000005];
int new_node(int prt,int L,int R) {
++tot;
v[tot].s.insert(rd[1]);
v[tot].lc=v[tot].rc=1,v[tot].prt=prt;
v[tot].stag=v[tot].stagc=v[tot].sum=0;
v[tot].lenc=v[tot].len=(R-L+1)%mod;
return tot;
}
void push_up(int x,int L,int R) {
int mid=(L+R)>>1;
if(!v[x].ls)v[x].ls=new_node(x,L,mid);
if(!v[x].rs)v[x].rs=new_node(x,mid+1,R);
v[x].lenc=((v[x].lc?v[v[x].ls].lenc:0)+(v[x].rc?v[v[x].rs].lenc:0))%mod;
v[x].sum=(v[v[x].ls].sum+v[v[x].rs].sum)%mod;
}
void upd_sum(int &x,long long val,int L,int R,int prt) {
if(!x)x=new_node(prt,L,R);
v[x].stag=(v[x].stag+val)%mod;
v[x].sum=(v[x].sum+v[x].lenc*val%mod)%mod;
}
void upd_sumc(int &x,long long val,int L,int R,int prt) {
if(!x)x=new_node(prt,L,R);
v[x].stagc=(v[x].stagc+val)%mod;
v[x].sum=(v[x].sum+(v[x].len-v[x].lenc)*val%mod)%mod;
}
void push_down(int x,int L,int R) {
int mid=(L+R)>>1;
if(v[x].stag) {
if(v[x].lc)upd_sum(v[x].ls,v[x].stag,L,mid,x);
if(v[x].rc)upd_sum(v[x].rs,v[x].stag,mid+1,R,x);
v[x].stag=0;
}
if(v[x].stagc) {
if(!v[x].lc)upd_sum(v[x].ls,v[x].stagc,L,mid,x);
if(!v[x].rc)upd_sum(v[x].rs,v[x].stagc,mid+1,R,x);
upd_sumc(v[x].ls,v[x].stagc,L,mid,x);
upd_sumc(v[x].rs,v[x].stagc,mid+1,R,x);
v[x].stagc=0;
}
}
void modify_sumc(int &x,int l,int r,long long val,int k,int prt,int L=1,int R=1e9) {
if(!x)x=new_node(prt,L,R);
if(l<=L&&R<=r) {
upd_sumc(x,val,L,R,prt);
if(rd[k]<*v[x].s.rbegin())upd_sum(x,val,L,R,prt);
return;
}
push_down(x,L,R);
int mid=(L+R)>>1;
if(l<=mid)modify_sumc(v[x].ls,l,r,val,k,x,L,mid);
if(mid<r)modify_sumc(v[x].rs,l,r,val,k,x,mid+1,R);
push_up(x,L,R);
}
void modify_sum(int &x,int l,int r,long long val,int k,int prt,int L=1,int R=1e9) {
if(!x)x=new_node(prt,L,R);
if(l<=L&&R<=r) {
if(rd[k]==*v[x].s.rbegin())upd_sum(x,val,L,R,prt);
return;
}
push_down(x,L,R);
int mid=(L+R)>>1;
if(l<=mid)modify_sum(v[x].ls,l,r,val,k,x,L,mid);
if(mid<r)modify_sum(v[x].rs,l,r,val,k,x,mid+1,R);
push_up(x,L,R);
}
long long ask(int &x,int l,int r,int prt,int L=1,int R=1e9) {
if(!x)x=new_node(prt,L,R);
if(l<=L&&R<=r)return v[x].sum;
long long ret=0;
push_down(x,L,R);
int mid=(L+R)>>1;
if(l<=mid)ret=(ret+ask(v[x].ls,l,r,x,L,mid))%mod;
if(mid<r)ret=(ret+ask(v[x].rs,l,r,x,mid+1,R))%mod;
return ret;
}
void Cut(int &x,int l,int r,int k,int prt,int L=1,int R=1e9) {
if(!x)x=new_node(prt,L,R);
if(l<=L&&R<=r) {
v[x].s.insert(rd[k]);
if(*v[x].s.rbegin()!=*v[v[x].prt].s.rbegin()) {
if(x==v[v[x].prt].ls)v[v[x].prt].lc=0;
else v[v[x].prt].rc=0;
}
return;
}
push_down(x,L,R);
int mid=(L+R)>>1;
if(l<=mid)Cut(v[x].ls,l,r,k,x,L,mid);
if(mid<r)Cut(v[x].rs,l,r,k,x,mid+1,R);
push_up(x,L,R);
}
void Link(int &x,int l,int r,int k,int prt,int L=1,int R=1e9) {
if(!x)x=new_node(prt,L,R);
if(l<=L&&R<=r) {
v[x].s.erase(rd[k]);
if(*v[x].s.rbegin()<=*v[v[x].prt].s.rbegin()) {
if(x==v[v[x].prt].ls)v[v[x].prt].lc=1;
else v[v[x].prt].rc=1;
}
return;
}
push_down(x,L,R);
int mid=(L+R)>>1;
if(l<=mid)Link(v[x].ls,l,r,k,x,L,mid);
if(mid<r)Link(v[x].rs,l,r,k,x,mid+1,R);
push_up(x,L,R);
}
} S;
int last_ans;
int main() {
n=getint();
Q=getint();
rd[1]=1,cd[1]=n;
for(int i=1; i<=Q; i++) {
int opt=getint();
if(opt==1) {
int k=getint();
long long val=getint();
S.modify_sum(root,rd[k],cd[k],val,k,0);
}
if(opt==2) {
int k=getint();
long long val=getint();
S.modify_sumc(root,rd[k],cd[k],val,k,0);
}
if(opt==3) {
int l=getint(),r=getint();
wrt(last_ans=S.ask(root,l,r,0)),pc('\n');
}
if(opt==4) {
int l=getint()^last_ans,r=getint()^last_ans,k=getint();
rd[k]=l,cd[k]=r;
S.Cut(root,rd[k],cd[k],k,0);
}
if(opt==5) {
int k=getint();
S.Link(root,rd[k],cd[k],k,0);
}
}
fwrite(wb,1,p2,stdout);
return 0;
}
京公网安备 11010502036488号