题解：CF794G Replace All

· · 题解

追赶 hanghang 的脚步！！其实不是非常困难。

考虑一个 \texttt{A,B} 确定的方案数。首先去掉相同的前缀后缀 \texttt{AB}，设 |S|>|T|，则（+ 表示拼接）：

S=T+S'

进一步的，目前前缀被替换成了 \texttt{BA'}\dots 和 \texttt{BB}\ \dots，这样又可以考虑 A' 和 B 的关系。

这不是更相减损术吗？最后直到 |S^{(k_1)}|=|T^{(k_2)}|=(|S|,|T|) 停止。此时被拆分为了长度为 (|S|,|T|) 的单位，每个位置无限制或限制两个单位相等（只有 S^{(k_1)},T^{(k_2)} 两个单位）。

显然，无限制当且仅当原串全同。而有限制时一个单位任取，因此非全同的方案数就是

2^{\gcd(|S|,|T|)}

然后设 \texttt{A,B,?} 在第一、二串分别有 a,b,c,A,B,C 个。我的唯一限制（目前不考虑全同）是 S,T 的大小关系 t_1|S|=t_2|T|。这个方程的贡献是

2^{\lfloor \frac{n(t_1,t_2)}{\max(t_1,t_2)}\rfloor+1}-2

然后设第一、二串选了 x,y 个 A。此时

t_1=a-A+x-y,t_2=B+C-b-c+x-y

这只跟 x-y 有关！只需枚举 x-y，这个 x,y 带来方案数是 \binom{C+c}{C+x-y}。

计算 t_1,t_2 之后正负性不相等直接没有任何方案。唯一产生问题，即不能直接计算是 t_1=t_2=0，即此时长度是任意的，需求：

\sum_{i,j\le n}2^{(i,j)}

这是容易数论分块套数论分块 O(n^{\frac 34}) 计算的，虽然代码里是 O(n\sqrt n)。

最后全同处理一下就可以了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=6e5+5,mod=1e9+7;
int n,m,lim,fac[maxn],ifac[maxn],A,B,C,a,b,c,N=6e5,t[maxn],dt=3e5,pw[maxn];
int Bi(int a,int b){
    if(b>a||b<0)return 0;
    return fac[a]*ifac[b]%mod*ifac[a-b]%mod;
}
int qp(int a,int b){
    if(b==0)return 1;
    int T=qp(a,b>>1);T=T*T%mod;
    if(b&1)T=T*a%mod;
    return T;
}
string S,T;
int sig(int x){return (x>0)-(x<0);}
int S2(int x){return pw[x+1]-1;}
int mu[maxn],isp[maxn];
vector<int> pr;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    fac[0]=1;for(int i=1;i<=N;i++)fac[i]=fac[i-1]*i%mod;
    ifac[N]=qp(fac[N],mod-2);
    for(int i=N-1;i>=0;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
    pw[0]=1;for(int i=1;i<=N;i++)pw[i]=pw[i-1]*2%mod;
    mu[1]=1;
    for(int i=2;i<=N;i++){
        if(!isp[i])pr.push_back(i),mu[i]=-1;
        for(auto u:pr){
            if(i*u>N)break;
            isp[i*u]=1;
            if(i%u==0){mu[i*u]=0;break;}
            mu[i*u]=mu[i]*mu[u];
        }
    }
    cin>>S>>T;n=S.length();m=T.length();cin>>lim;
    for(int i=0;i<n;i++)a+=(S[i]=='A'),b+=(S[i]=='B'),c+=(S[i]=='?');
    for(int i=0;i<m;i++)A+=(T[i]=='A'),B+=(T[i]=='B'),C+=(T[i]=='?');
    for(int i=-C;i<=c;i++)t[i+dt]=Bi(c+C,C+i);
    int ans=0,qsy=0;
    for(int l=1,r;l<=lim;l=r+1){
        r=lim/(lim/l);
        int res=0;
        for(int j=1;j<=lim/l;j++)(res+=mu[j]*((lim/l)/j)%mod*((lim/l)/j))%=mod;
        (qsy+=res*(S2(r)-S2(l-1)+mod)%mod)%=mod;
    }
    // for(int i=1;i<=lim;i++)for(int j=1;j<=lim;j++)(qsy+=pw[__gcd(i,j)])%=mod;
    for(int i=-C;i<=c;i++){
        int c1=a-A+i,c2=B+C-b-c+i;
        if(sig(c1)!=sig(c2))continue;
        // cout<<i<<" "<<c1<<" "<<c2<<" "<<t[i+dt]<<endl;
        if(sig(c1)==1){
            if(c1<c2)swap(c1,c2);
            (ans+=(pw[lim/(c1/__gcd(c1,c2))+1]-2)*t[dt+i])%=mod;
        }else if(sig(c1)==-1){
            c1=-c1,c2=-c2;
            if(c1<c2)swap(c1,c2);
            (ans+=(pw[lim/(c1/__gcd(c1,c2))+1]-2)*t[dt+i])%=mod;
        }else{
            (ans+=qsy*t[dt+i])%=mod;
        }
    }
    if(n==m){
        bool flg=1;int cnt=0;
        for(int i=1;i<=n;i++){
            if(S[i-1]!='?'&&S[i-1]!=T[i-1]&&T[i-1]!='?'){flg=0;break;}
            if(S[i-1]==T[i-1]&&S[i-1]=='?')++cnt;
        }
        if(flg){
            (ans+=((pw[lim+1]-2)*(pw[lim+1]-2)%mod+mod-qsy)*pw[cnt])%=mod;
        }
    }
    cout<<ans<<endl;
    return 0;
}