题解：CF2174C1 Beautiful Patterns (Easy Version)

thousands_of_years · 2026-01-04 18:02:23 · 题解

solution

首先我们把要求的东西转化成两个子串都是回文串的期望，这是显然的。

而单个回文串的期望是又是 m^{-\lfloor len/2 \rfloor}，证明就是确认回文中心一边后，另一边确定，在图论角度上就是总连通块数除上总点数。

而你需要发现一个性质两个回文中心不同子串都是回文串的期望就是任意两个串的回文期望乘起来即可。

证明：当两个串不相交时，两个串互不影响，直接乘上，而两个串相交时，转成图是没有环的，在没有环的情况下，每一条边都是把两个不连通的连通块连起的，所以总点数与连通块数的差值就是边的个数，而边数就是 \lfloor len1/2 \rfloor+\lfloor len2/2 \rfloor。

至于为什么无环，感性理解一下，你从两个对称中心之间的点出发，由于是交替使用不同种边，每次是越来越远的，所以无环。

麻烦的是回文中心相同的子串是，取 m^{-\lfloor \max(len1,len2)/2 \rfloor}，从图论角度就是长度更小的子串连的边会与大的形成环，连通块数量不变。

我们按奇偶分组，求出单个子串的长度后缀和。奇偶不同的子串回文中心不可能相同，两者直接相乘，还要乘个二。

然后枚举长度，将同奇偶还比自己长度长的子串期望和乘上自己与他奇偶中心没有重合的期望，重合时只算比自己长的串的期望，于是还要再加上字串期望和，由于这位置可以互换，所以这部分总体乘上二。

同一长度的不能互换，与上方推理类似。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+9,inf=1e9+7,lenn=1e9+7;
int T,n,m,p,v[3][N];
int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
signed main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>p;
        int sum=0,res=0;
        for(int i=1;i<=n+10;i++)
            v[0][i]=v[1][i]=0;
        for(int i=n;i>=1;i--)
        {
            v[i&1][(i+1)/2]=(v[i&1][(i+3)/2]+qpow(qpow(m,(i)/2),p-2)*(n-i+1))%p;
            v[i&1][(i+1)/2]%=p;
        }
        sum=v[1&1][(1+1)/2]*v[(2)&1][(2+1)/2]%p*2%p;
        for(int i=1;i<=n;i++)
        {
            res=v[i&1][(i+3)/2]*(qpow(qpow(m,(i)/2),p-2)%p*(n-i)%p+1)%p*2%p;
            sum+=res;
            sum%=p;
            res=qpow(qpow(m,(i)/2),p-2)*(n-i+1)%p*qpow(qpow(m,(i)/2),p-2)%p*(n-i)%p;
            sum+=res;
            sum%=p;
            res=(n-i+1)*qpow(qpow(m,(i)/2),p-2)%p;
            sum+=res;
            sum%=p;
        }
        cout<<sum<<endl;
    }
    return 0;
}