# 【题解】牛客挑战赛50 精

【题解】牛客挑战赛50
@[toc]
UPD: 非常抱歉，C题数据弱了，在回文树上暴力跳父亲的代码是不应该通过的，数据已增强。

# A Red and Blue and Green

```#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
typedef unsigned long long ull;
typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define nep(i,r,l) for(int i=r;i>=l;i--)
void sc(int &x){scanf("%d",&x);}
void sc(int &x,int &y){scanf("%d%d",&x,&y);}
void sc(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}
void sc(ll &x){scanf("%lld",&x);}
void sc(ll &x,ll &y){scanf("%lld%lld",&x,&y);}
void sc(ll &x,ll &y,ll &z){scanf("%lld%lld%lld",&x,&y,&z);}
void sc(char *x){scanf("%s",x);}
void sc(char *x,char *y){scanf("%s%s",x,y);}
void sc(char *x,char *y,char *z){scanf("%s%s%s",x,y,z);}
void out(int x){printf("%d\n",x);}
void out(ll x){printf("%lld\n",x);}
void out(int x,int y){printf("%d %d\n",x,y);}
void out(ll x,ll y){printf("%lld %lld\n",x,y);}
void out(int x,int y,int z){printf("%d %d %d\n",x,y,z);}
void out(ll x,ll y,ll z){printf("%lld %lld %lld\n",x,y,z);}
using namespace std;
const int N=2e5+5;
int n;
char s[N];
int main()
{

//freopen("1.in","r",stdin);freopen("1.out","w",stdout);mod=998244353;
sc(n);
sc(s+1);
for(int i=2;i<=n;i+=2)
{
s[i]='R';
if(s[i]==s[i-1]||s[i]==s[i+1]) s[i]='G';
if(s[i]==s[i-1]||s[i]==s[i+1]) s[i]='B';
}
printf("%s\n",s+1);
}
```

# B Random eat Cake

\$\$

，答案为

```#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,N=5e5+5;
typedef long long ll;
ll n,inv[N],p2[N],p[N];
ll qpow(ll a,ll n)
{
ll ans=1;
for(;n;n>>=1,a=a*a%mod)
if(n&1) ans=ans*a%mod;
return ans;
}
int main()
{
p[0]=1;
p2[0]=inv[1]=1;for(int i=1;i<N;i++) p2[i]=p2[i-1]*2%mod;
for(int i=2;i<N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<N;i++) p[i]=(p2[i]+(i-1)*p2[max(0,i-2)])%mod;
int t;scanf("%d",&t);
ll sss=0;
while(t--)
{
scanf("%lld",&n);
ll ans=0,res=1;
for(int k=1;k<=n;k++)
{
res=res*inv[k]%mod;
ans=(ans+res*p[n-k])%mod;
}
ans=ans*qpow(p2[n-1],mod-2)%mod;
printf("%lld\n",ans);
}
}
```

# C k-palindrome

## solution1 马拉车算法

```#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
typedef unsigned long long ull;
typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define nep(i,r,l) for(int i=r;i>=l;i--)
void sc(int &x){scanf("%d",&x);}
void sc(int &x,int &y){scanf("%d%d",&x,&y);}
void sc(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}
void sc(ll &x){scanf("%lld",&x);}
void sc(ll &x,ll &y){scanf("%lld%lld",&x,&y);}
void sc(ll &x,ll &y,ll &z){scanf("%lld%lld%lld",&x,&y,&z);}
void sc(char *x){scanf("%s",x);}
void sc(char *x,char *y){scanf("%s%s",x,y);}
void sc(char *x,char *y,char *z){scanf("%s%s%s",x,y,z);}
void out(int x){printf("%d\n",x);}
void out(ll x){printf("%lld\n",x);}
void out(int x,int y){printf("%d %d\n",x,y);}
void out(ll x,ll y){printf("%lld %lld\n",x,y);}
void out(int x,int y,int z){printf("%d %d %d\n",x,y,z);}
void out(ll x,ll y,ll z){printf("%lld %lld %lld\n",x,y,z);}
using namespace std;
const int N=5e5+5,mod1=998244353,mod2=1e9+7;
const int b1=233,b2=3993;
ll f1[N],f2[N],hs1[N],hs2[N];
int n,m,p[N],ans[N];
char s[N],t[N];
void iniths(ll hs[N],int b,int mod)
{
rep(i,1,n)
hs[i]=(hs[i-1]*b%mod+s[i]-'a'+1)%mod;
}
int geths(int l,int r,ll hs[N],ll f[N],int mod)
{
return (hs[r]-hs[l-1]*f[r-l+1]%mod+mod)%mod;
}
ll geths(int l,int r)
{
return geths(l,r,hs1,f1,mod1)*2000000000ll+geths(l,r,hs2,f2,mod2);
}
unordered_map<ll,int>lev;
void update(int l,int r)
{
if(l==r) lev[geths(l,r)]=1;
else lev[geths(l,r)]=lev[geths(l,(l+r-1)/2)]+1;
}
void MLC()
{
t[1]='\$';
rep(i,1,n)
t[i<<1]=s[i],t[i<<1|1]='#';
t[(n+1)*2]='*';
int id=0,r=0;
for(int i=1;i<=n*2+1;i++)
{
if(i<=r) p[i]=min(r-i,p[id-(i-id)]);
while(t[i-p[i]]==t[i+p[i]])
{
p[i]++;
int len=(p[i]+(i%2==0))/2-1;
if(len<0) continue;
if(i&1) update(i/2-len,(i+1)/2+len);
else update(i/2-len,i/2+len);
}
if(i+p[i]>r)
id=i,r=i+p[i];
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
f1[0]=f2[0]=1;
rep(i,1,N-1) f1[i]=f1[i-1]*b1%mod1,f2[i]=f2[i-1]*b2%mod2;
int t;sc(t);
while(t--)
{
sc(n,m);
rep(i,1,n) ans[i]=0;
sc(s+1);
iniths(hs1,b1,mod1);
iniths(hs2,b2,mod2);
lev.clear();
MLC();
for(auto it=lev.begin();it!=lev.end();it++)
ans[it->second]++;
nep(i,n-1,1) ans[i]=(ans[i]+ans[i+1])%mod1;
int res=0,p=1;
rep(i,1,m)
{
p=p<<1%mod1;
res=(res+1ll*p*ans[i])%mod1;
}
res=(res+mod1)%mod1;
out(res);
}
}```

## solution2 回文树

```#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+5,M=26;
char s[N];
int n,m,lg[N];
ll ans[N];
struct Palindromic_tree
{
int tot,last,n,nex[N][M],dep[N],k_th[N],fail[N][20],len[N],num[N],cnt[N],s[N];
int newnode()
{
tot++;memset(nex[tot],0,sizeof(nex[tot]));
memset(fail[tot],0,sizeof(fail[tot]));
len[tot]=num[tot]=cnt[tot]=0;
}
void init()
{
tot=-1;newnode();newnode();
len[1]=-1;fail[0][0]=1;last=n=0;s[n]=-1;
}
int getf(int x)
{
while(s[n-len[x]-1]!=s[n]) x=fail[x][0];return x;
}
int getf(int x,int l)
{
for(int i=lg[num[x]];i>=0;i--)
if(len[fail[x][i]]>=l)
x=fail[x][i];
return x;
}
{
s[++n]=c;
int cur=getf(last);
if(!nex[cur][c])
{
int now=newnode();
len[now]=len[cur]+2;
fail[now][0]=nex[getf(fail[cur][0])][c];
nex[cur][c]=now;
num[now]=num[fail[now][0]]+1;
for(int i=1;1<<i<=num[now];i++)
fail[now][i]=fail[fail[now][i-1]][i-1];
int x=getf(now,len[now]/2);
if(len[x]==len[now]/2)
k_th[now]=k_th[x]+1;
else k_th[now]=1;
}
last=nex[cur][c];
cnt[last]++;
}
void count()
{
for(int i=tot;i>=2;i--)
cnt[fail[i][0]]+=cnt[i];
}
void getAns()
{
for(int i=2;i<=tot;i++)
ans[k_th[i]]++;
for(int i=n-1;i>=1;i--)
ans[i]+=ans[i+1];
}
}A;
int main()
{
//freopen("17.in","r",stdin);
for(int i=1;i<N;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
for(int i=1;i<N;i++) lg[i]--;
int t;scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) ans[i]=0;
scanf("%s",s+1);
A.init();
for(int i=1;i<=n;i++)
A.getAns();
int res=0,p=1;
for(int i=1;i<=m;i++)
{
p=(p<<1)%998244353;
res=(res+1ll*ans[i]*p)%998244353;
}
printf("%d\n",res);
}
}```

# D Derivation of polynomials

```#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2005,mod=998244353,G=3,Gi=332748118;
int n,m,k,rev[N<<2],a[N<<2],b[N<<2],c[N<<2];
ll qpow(ll a,ll n)
{
ll ans=1;
while(n)
{
if(n&1) ans=ans*a%mod;
a=a*a%mod;
n>>=1;
}
return ans;
}
void NTT(int *f,int n,int opt)
{
for(int i=0;i<n;i++)
if(i<rev[i]) swap(f[i],f[rev[i]]);
for(int l=2,k=1;l<=n;l<<=1,k<<=1)
{
ll w=qpow(opt==1?G:Gi,(mod-1)/l);
for(int i=0;i<n;i+=l)
{
ll wi=1;
for(int j=0;j<k;j++,wi=wi*w%mod)
{
ll b=wi*f[i+j+k]%mod;
f[i+j+k]=(f[i+j]-b+mod)%mod;
f[i+j]=(f[i+j]+b)%mod;
}
}
}
}
int len=1,bit=0;
ll invlen;
int main()
{
//freopen("1.in","r",stdin);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i-1]),a[i-1]=1ll*i*a[i-1]%mod;
for(int i=1;i<=m;i++) scanf("%d",&b[i]);
int ans=0;
while(len<=n-1+k) len<<=1,bit++;
for(int i=0;i<len;i++)
rev[i]=(rev[i>>1]>>1)|((i&1)<<bit-1);
invlen=qpow(len,mod-2);
NTT(a,len,1);
for(int t=1;t<=k;t++)
{
for(int i=0;i<=k;i++) c[i]=b[i];
for(int i=k+1;i<len;i++) c[i]=0;
NTT(c,len,1);
for(int i=0;i<len;i++) c[i]=(ll)c[i]*a[i]%mod;
NTT(c,len,mod-1);
for(int i=0;i<=k;i++) c[i]=c[i]*invlen%mod;
for(int i=0;i<=k;i++)
b[i]=(1ll*b[i+1]*(i+1)+c[i])%mod;
ans=(ans+b[0])%mod;
}
printf("%d\n",ans);
}```

# E XYZ Problem

```#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll X,Y,Z,A,L,R;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;y=0;return a;
}
ll ans=exgcd(b,a%b,x,y);
ll t=x;x=y;y=t-a/b*y;
return ans;
}
pair<ll,ll> S(ll X,ll A,ll Z,ll L,ll R)
{
ll x,y,g=exgcd(X,Z,x,y);
if(g<0) g*=-1;
if(A%g) return {-1,-1};
ll r=Z/g;
x=(A/g*x%r+r)%r;
if(x<L)
{
x=x+(L-x)/r*r;
if(x<L) x+=r;
}
if(x>R) return {-1,-1};
return {x,r};
}
int main()
{
int t;scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%lld%lld%lld%lld",&X,&Y,&Z,&A,&L,&R);
ll ans=R-L+1;
pair<ll,ll>p1=S(X,A,Z,L,R),p2=S(Y,A,Z,L,R);
if(p1.first!=-1)
ans-=1+(R-p1.first)/p1.second;
if(p2.first!=-1)
ans-=1+(R-p2.first)/p2.second;
if(p1.first!=-1&&p2.first!=-1)
{
if(p1.first<p2.first) swap(p1,p2);
ll x1=p1.first,x2=p2.first,c1=p1.second,c2=p2.second;
ll R1=(R-x1)/c1,R2=(R-x2)/c2;
pair<ll,ll>p=S(-c1,x1-x2,c2,0,R1);
if(p.first!=-1)
{
ll x=p.first,rx=p.second;
ll y=((x1-x2)+c1*x)/c2,ry=c1/__gcd(c1,c2);
if(y<=R2)
ans+=1+min((R1-x)/rx,(R2-y)/ry);
}
}
printf("%lld\n",ans);
}
}```

# F Alice, Bob and Play Game

1.是限制关系，添加一个新的限制关系

2.是限制关系，添加一个新的限制关系，通过合理的操作，我们可以把其改成新的限制关系，删除限制关系

```#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef long long ll;
int n,q,opt[N],g[N],vis[N];
vector<int>f[N][2];
char ans[N];
void Set(int x)
{
ans[x>>1]=(x&1)+'0';
for(int y:f[x>>1][x&1]) Set(y);
}
{
f[x>>1][x&1].push_back(y);
}
int main()
{
scanf("%d%d",&n,&q);
int res=n;
for(int i=1;i<=q;i++)
{
int u,v;scanf("%d%d",&u,&v);
if(!vis[u]&&!vis[v])
{
vis[u]=v;vis[v]=u;
opt[u]=i<<1|1;
opt[v]=i<<1;
res--;
}
else if(vis[u]&&vis[v])
{
if(vis[u]==v)
Set(opt[rand()&1?u:v]);
else
{
int _u=vis[u],_v=vis[v];
vis[_u]=vis[v];
vis[_v]=vis[u];
vis[u]=v;vis[v]=u;
}
opt[u]=i<<1;
opt[v]=i<<1|1;
}
else if(vis[u])
{
Set(opt[vis[u]]);
vis[vis[u]]=0;
vis[u]=v;vis[v]=u;
opt[u]=i<<1;
opt[v]=i<<1|1;
}
else if(vis[v])
{
Set(opt[vis[v]]);
vis[vis[v]]=0;
vis[u]=v;vis[v]=u;
opt[u]=i<<1;
opt[v]=i<<1|1;
}
g[i]=res;
}
for(int i=1;i<=n;i++)
if(vis[i])
{
Set(opt[i]);
vis[vis[i]]=0;
vis[i]=0;
}
for(int i=1;i<=q;i++)
printf(i==q?"%d\n":"%d ",g[i]);
for(int i=1;i<=q;i++) putchar(ans[i]);
putchar('\n');
}
```

# G Travel on M-ary tree

1.随机生成一个结点，求的期望值。
2.随机生成两个结点，求的期望值。

## 问题二解法

```#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll n,M,k;
ll qpow(ll a,ll n)
{
ll ans=1;
for(;n;n>>=1,a=a*a%mod)
if(n&1) ans=ans*a%mod;
return ans;
}
struct node
{
ll a[3][3];
node(){memset(a,0,sizeof(a));}
node operator*(const node&B)const
{
node ans;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
for(int k=0;k<3;k++)
ans.a[i][j]=(ans.a[i][j]+a[i][k]*B.a[k][j])%mod;
return ans;
}
};
node qpow(node a,ll n)
{
node ans;for(int i=0;i<3;i++) ans.a[i][i]=1;
for(;n;n>>=1,a=a*a)
if(n&1) ans=ans*a;
return ans;
}
ll f(ll n)
{
node A;
A.a[0][0]=A.a[2][2]=M;
A.a[1][0]=A.a[1][1]=A.a[2][1]=1;
A=qpow(A,n-1);
ll ans=M*(A.a[1][0]+M*A.a[2][0]%mod)%mod;
return ans;
}
ll g(ll n)
{
return (qpow(M,n)-1)*qpow(M-1,mod-2)%mod;
}
ll P(ll n)
{
ll ans=(n-1)*qpow(M,n)%mod*g(n)%mod;
ans=(ans-qpow(M,n)*qpow(M-1,mod-2)%mod*(g(n)-n))%mod;
ans=(ans+mod)%mod;
return ans;
}
ll S(ll n)
{
return g(n)*(g(n)-1)%mod;
}
ll U(ll n)
{
ll ans=(n-1)*qpow(M,n)%mod-g(n)+1;
ans=ans%mod*qpow(M-1,mod-2)%mod;
ans=(ans+mod)%mod;
return ans;
}
ll Res()
{
ll res=2*qpow(M-1,mod-2)%mod*((P(n)-S(n)+U(n))%mod)%mod;
res=(res+mod)%mod;
return res;
}
ll sum2(ll n)
{
return n*(n+1)%mod*(2*n%mod+1)%mod*qpow(6,mod-2)%mod;
}
void aa(ll x,ll l,ll r)
{
assert(x>=l&&x<=r);
}
int main()
{
//freopen("1.in","r",stdin);
int t;scanf("%d",&t);
aa(t,1,20000);
while(t--)
{
scanf("%lld%lld%lld",&n,&M,&k);
aa(n,1,1000000000);
aa(M,1,1000000000);
aa(k,1,1000000);
k--;
if(M==1)
{
ll invg=qpow(n,mod-2)%mod;
ll fn=n*(n-1)/2%mod;
ll res=fn*n%mod-sum2(n-1);
res=(res*2%mod+mod)%mod;
ll ans=(fn*invg+res*invg%mod*invg%mod*k%mod)%mod;
printf("%lld\n",ans);
continue;
}
ll invg=qpow(g(n),mod-2);
ll ans=(f(n)*invg%mod+Res()*invg%mod*invg%mod*k%mod)%mod;
printf("%lld\n",ans);
}
}```

# 近期热帖

• 回复(0) 发表于 今天 11:32:27
• 回复(1) 发表于 2021-07-25 14:23:23

# 等你来战

• 报名截止时间：2021-07-26 17:00
• 报名截止时间：2021-07-27 17:00
• 报名截止时间：2021-07-31 17:00
• 报名截止时间：2021-08-02 17:00
• 报名截止时间：2021-08-03 17:00
• 报名截止时间：2021-08-05 22:00
• 报名截止时间：2021-08-07 17:00
• 报名截止时间：2021-08-09 17:00
• 报名截止时间：2021-08-10 17:00
• 报名截止时间：2021-08-12 17:00
• 报名截止时间：2021-08-12 22:00
• 报名截止时间：2021-08-14 17:00
• 报名截止时间：2021-08-16 17:00
• 报名截止时间：2021-08-19 17:00
• 报名截止时间：2021-08-21 17:00
• 报名截止时间：2021-08-26 17:00
• 报名截止时间：2021-08-28 17:00
• 报名截止时间：2021-08-31 17:00

# 热门推荐

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题