Huah

编辑于 2021-05-14 23:20

+ 关注

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

考虑计算一次性吃下 ${x(x\in \{1,2,...,n\})}$ 块蛋糕的概率：
由隔板法， $n$ 块蛋糕能够生成的序列的数量为：
$ ${g(n)=2^{n-1}(n\ge 1)},g(0)=1$ $

设一次吃 $k$ 块蛋糕的概率为 $f(k)$ ，枚举这 $k$ 块蛋糕左右的蛋糕数得 $f(k)=\sum_{i=k}^n\frac{g(i-k)g(n-i)}{g(n)}\\=\frac{1}{g(n)}(2^{n-k}+(n-k-1)2^{n-k-2})$
令 $P(x)=2^x+(x-1)2^{x-2}(P(0)=1)$ ，答案为 $ans(n)=\sum\limits_{k=1}^n\frac{f(k)}{k!}=\frac{1}{g(n)}\sum_{k=1}^n\frac{p(n-k)}{k!}$
预处理 $P(x)$ 和逆元，可以在 $O(n)$ 的时间内得出答案。
看到过题里面还有递推的解法，欢迎大家分享题解！

#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 马拉车算法

若 $S_1S_2...S_n$ 为回文且 $S_1S_2...S_{\lfloor\frac{n}{2}}\rfloor$ 为回文，由回文的对称性得 $S_1S_2...S_{\lfloor\frac{n}{2}\rfloor}=S_{n-\lfloor\frac{n}{2}\rfloor+1}...S_{n-1}S_n$ 。
注意到题目这个规定使得 $(k+1)-palindrome$ 也是 $k-palindrome$ ，不妨把某个回文能满足的最大的 $k-palindrome$ 称为这个回文的等级，特别的定义空串和非回文串的等级为 $0$ 。
令 $S[l:r]$ 表示 $S_lS_{l+1}...S_r$ 构成的字符串， $lev(S)$ 表示字符串 $S$ 的等级。则 $lev(S[l:r])=l==r?1:lev(S[l,\lfloor\frac{l+r-1}{2}\rfloor])+1$
这要求 $lev(S[l,\lfloor\frac{l+r-1}{2}\rfloor])$ 比 $lev(S[l:r])$ 先求出来，发现马拉车求回文半径的过程中每次得到的回文区间满足这个条件，再加上本质不同这个条件，我们可以用字符串哈希来表示一个回文串，时间复杂度 $O(n)$ 。

#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 回文树

另一个方法就是回文树了，发现回文树更新的过程也满足 $lev(S[l,\lfloor\frac{l+r-1}{2}\rfloor])$ 比 $lev(S[l:r])$ 先更新，可以在回文树上倍增得到 $S[l:r]$ 长度为 $\lfloor\frac{r-l+1}{2}\rfloor$ 的回文祖先，该结点的等级为其长度为 $\lfloor\frac{r-l+1}{2}\rfloor$ 的回文祖先的等级 $+1$ ，如果这样的祖先不存在，则该节点的等级为 $1$ ，时间复杂度 $O(n)$ ，特别的回文树的两个起始结点等级为 $0$ 。

#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

令 $dp_{i,j}$ 为第 $i$ 次求导， $x^je^{g(x)}$ 的系数，按求导法则进行递推即可，答案为 $\sum\limits_{i=0}^kdp_{i,0}$ ，注意到当 $j>k$ 时不需要维护，时间复杂度为 $O(n^3)$ ，不足以通过此题。
观察 $dp$ 的转移，实际上，令多项式 $A=\sum\limits_{i=0}^{n-1}(i+1)a_{i+1}x^i$ ，把 $dp_i$ 看作一个 $k$ 次多项式 $F_i=\sum\limits_{j=0}^kdp_{i,j}x^j$ ，有 $F_{i+1}=F_i*A+(F_i)'$ 。
对于 $F_i*A$ ，用 $NTT$ 加速， $(F_i)'$ 直接计算，时间复杂度为 $O(n^2log_2(n))$ 。

此外也可以直接根据求导法则推导：这个多项式是 $F(x)e^{G(x)}$ 的形式 $(F(x)e^{G(x)})'=(F(x)*G'(X)+F'(x))e^{G(x)}$

过题里面还有不一样的解法，欢迎大家分享题解！

#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

问题等价与求 $\sum_{i=L}^R[(X*i-A)\bmod Z\neq 0][(Y*i-A)\bmod Z\neq 0]\\=R-L+1-\sum_{i=L}^R[X*i\bmod Z= A]|[Y*i\bmod Z= A]$
令 $S=\sum\limits_{i=L}^R[X*i\bmod Z=A]+\sum\limits_{i=L}^R[Y*i\bmod Z=A]\\T=\sum_{i=L}^R[X*i\bmod Z=A]\&[Y*i\bmod Z=A]$
答案为 $R-L+1+S-T$ 。
令 $x_1,c_1$ 分别为方程 $x*X+y*Z=A$ 满足 $L\le x_1\le R$ 的最小正整数解和周期， $x_2,c_2$ 为方程 $x*Y+y*Z=A$ 的。则 $S=2+\lfloor\frac{R-x_1}{c_1}\rfloor+\lfloor\frac{R-x_2}{c_2}\rfloor$
对于 $T$ ，我们要找 $x_1+x*c_1=x_2+y*c_2\le R$ 的 $x,y$ 的对数，等价于 $x*(-c_1)+y*c_2=x_1-x_2$ ，且 $0\le x\le\lfloor\frac{R-x_1}{c_1}\rfloor,0\le y\le\lfloor\frac{R-x_2}{c_2}\rfloor$ 。
两者都可以采用扩展 $GCD$ 并利用周期性得出答案。
时间复杂度为 $O(Tlog_2(n))$ 。

#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

事实上，只要操作的两个点不全为 $0$ ，就必然能够使得在进行操作后的两个点其中一个为 $1$ ，另一个为 $0$ 。
但由于先进行的操作不知道后进行的操作会操作哪些点，故不能实时的就把操作的状态分配好。
事实上，只要操作的得当，任何时候都可以让被选择的两个点 $u,v$ ，其中一个为 $0$ ，另一个为 $1$ 。
如果添加了一条边，则 $u,v$ 之间只能一个取 $1$ ，考虑把 $u,v$ 之间的关系称为限制关系。
然后分以下情况讨论：
1. $u-v$ 是限制关系，添加一个新的限制关系 $v-w$
在这里插入图片描述
此时，不妨让 $u$ 为 $1$ ，删除限制关系 $u-v$ ，只形成限制关系 $v,w$ 。
2. $u-v,w-x$ 是限制关系，添加一个新的限制关系 $v,x$ ，通过合理的操作，我们可以把其改成新的限制关系 $u-w,v-x$ ，删除限制关系 $u-v,w-x$ 。
在这里插入图片描述
通过以上讨论，可以使得，任何限制关系都是成对的，处于限制关系中必有一个为 $1$ ，另一个为 $0$ ，且不处于限制关系中的必为 $1$ 。
这样只有在选择的两个结点的值都为 $1$ 的情况下才会使得总和减 $1$ 。

令 $opt_u=y$ 为让 $a_u=1$ 则第 $y>>1$ 条边必须执行操作 $y\&1$ ， $x\in f[y>>1][y\&1]$ 为让第 $y>>1$ 条边执行操作 $y\&1$ 则第 $x>>1$ 条边必须执行操作 $x\&1$ 。

#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.随机生成一个结点 $u$ ，求 $dis(1,u)$ 的期望值。
2.随机生成两个结点 $u,v$ ，求 $dis(u,v)$ 的期望值。

原问题实际上就是 $1$ 个问题一和 $k-1$ 个问题二。

问题一解法

考虑计算距离之和除以方案数，首先，对于一颗高度为 $n$ 的满 $M$ 叉树，其所有点到根结点的距离之和为 $f_(n)=\sum\limits_{i=1}^n(i-1)*M^{i-1}\\=M+2*M^2+...+(n-1)*M^{(n-1)}\\=(M+...+M^{n-1})+M*f_(n-1)$
这可以构造矩阵快速幂 $O(logn)$ 计算。
令 $g(n)=\sum\limits_{i=0}^{n-1}M^i=\frac{M^n-1}{M-1}$
问题一的期望距离为 $\frac{f(n)}{g(n)}$ 。

问题二解法

问题二中一条边 $s,t(s$ 为 $t$ 的父亲)被经过当前仅当 $u$ 在 $t$ 的子树， $v$ 不在 $t$ 的子树或者反之。
则距离和为 $res=2*\sum_{i=1}^{n-1}M^{n-i}*g(i)*(g(n)-g(i))=\\ \frac{2}{M-1}\sum_{i=1}^{n-1}M^{n-i}*(M^i-1)*(g(n)-g(i))=\\ \frac{2}{M-1}\sum_{i=1}^{n-1}(M^n-M^{n-i})*(g(n)-g(i))$
$\sum_{i=1}^{n-1}M^n*(g(n)-g(i))=(n-1)M^ng(n)-M^n\sum_{i=1}^{n-1}g(i)=\\ (n-1)M^ng(n)-\frac{M^n}{M-1}\sum_{i=1}^{n-1}(M^i-1)=\\ (n-1)M^ng(n)-\frac{M^n}{M-1}(g(n)-n)=P(n)$
$\sum_{i=1}^{n-1}M^{n-i}g(n)=g(n)\sum_{i=1}^{n-1}M^i=g(n)(g(n)-1)=S(n)$
$\sum_{i=1}^{n-1}M^{n-i}*g(i)=\frac{1}{M-1}\sum_{i=1}^{n-1}M^{n-i}(M^i-1)=\\\frac{1}{M-1}((n-1)*M^n-g(n)+1) =U(n)$
最后 $res=\frac{2}{M-1}(P(n)-S(n)+U(n))$
答案为 $ans=\frac{f(n)}{g(n)}+\frac{res}{g^2(n)}*(k-1)$
总的时间复杂度为 $O(logn)$ 。
此外，注意 $M=1$ 时的边界情况，当 $M=1$ 时： $f(n)=\frac{n*(n-1)}{2},res=\sum_{i=1}^{n-1}i(n-i)$

#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);
    }
}

2024最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(4) 回帖

加载中...

话题同步到我的动态回帖