竞赛讨论区 > 【题解】牛客挑战赛50

【题解】牛客挑战赛50

头像
Huah
编辑于 2021-05-14 23:20:28 APP内打开
赞 4 | 收藏 0 | 回复4 | 浏览1062

【题解】牛客挑战赛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

这题和牛客练习赛64F是孪生兄弟,很久以前这两道题的想法就一起诞生了,它们都可以用马拉车来做。

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;
        return tot;
    }
    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;
    }
    void add(int c)
    {
        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.add(s[i]-'a');
        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);
}
void add(int x,int 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
            {
                add(opt[vis[u]],opt[v]);
                add(opt[vis[v]],opt[u]);
                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);
    }
}

4条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐