# CF794G Replace All

Statement

给两个包含A,B,?的串，?可以是A或B，求所有？的情况下，求下面这个东西的和：统计有多少对长度 \(\le n\) 的01串 \((S,T)\) 使得把所有A换成 \(S\) ，B换成 \(T\) 使得两个串相等

\(n\le 3\times 10^5\) ，原串长度 \(\le 3\times 10^5\)

Solution

我们先考虑没有问号的情况。

记 \(A,B\) 表示原串，\(a,b\) 表示字符 \('A','B'\)

一. 若 \(A=B\)

那么显然这个时候 \(S,T\) 随意，方案数 \((\sum 2^i)^2\)

二. 若 \(A\ne B\)

以下不妨设 \(|S|<|T|\)

此时 \(S=T\) 或者 \(S\) 是 \(T\) 的前缀并且二者有公共循环节

\(S\) 和 \(T\) 有最小公共循环节 \(\gcd(|S|,|T|)\) ，并且 \(S[1\dots \gcd(|S|,|T|)]=T[1\dots \gcd(|S|,|T|)]\)

Proof

假设 \((S,T)\) 是符合题意的

我们找到 \(A,B\) 中第一个 \(A[i]\ne B[i]\) 的位置，由此可以知道 \(S,T\) 存在前缀关系，不妨设 \(|S|\le |T|\) ，那么知道 \(S\) 是 \(T\) 的前缀

考虑匹配的过程，从第一个 \(A[i]\ne B[i]\) 的位置开始匹配，设 \(T=cS+X\) （在 \(c\) 个 \(S\) 后面拼一个 \(X\))，显然 \(X\) 是 \(S\) 的一个前缀。

不妨把所有 \(T\) 都替换成 \(cS+X\) ，那么场上只剩下 \(S,X\) ，且我们知道 \(X\) 是 \(S\) 的前缀

令 \(S^{\prime}=X,T^{\prime}=S\) ，重复刚才的过程，因为把所有 \(a\) 换成 \(S\) ，\(b\) 换成 \(T\) 后两个串相等，所以最后一定会有 \(S^{\prime}=T^{\prime}\)

此时，观察上述过程 \(S,T\) 的长度变化，发现每一次相当于 \(|T|\%=|S|\) ，即辗转相除法求 \(\gcd\) 的过程，所以 \(S,T\) 都有公共循环节，循环节长度 \(\gcd(|S|,|T|)\)

所以我们可以通过 \(m\) 和 \(|S|,|T|\) 来确定 \(S,T\)

由于二者有公共循环节，所以 \(S+T=T+S\) ，也就是说，我们并不关注 \(a,b\) 的位置，我们只关注它们的数量

设 \(cnt_{a,A}\) 表示 \(A\) 中 \(a\) 的数量，那么我们现在只需要满足 \(cnt_{a,A}|S|+cnt_{b,A}|T|=cnt_{a,B}|S|+cnt_{b,B}|T|\) 即可

移一下项，得到 \((cnt_{a,A}-cnt_{a,B})|S|=(cnt_{b,B}-cnt_{b,A})|T|\)

记 \(ca=cnt_{a,A}-cnt_{a,B},cb=cnt_{b,B}-cnt_{b,A}\)，限制变为 \(ca|S|=cb|T|\)

① 若 \(ca=cb\)

\((i)\ ca=cb=0\) 这个时候的 \(S,T\) 就随意啦，只要满足有公共循环节即可，答案就是

\[\begin{align*} \sum_i^n\sum_j^n2^{\gcd(i,j)}&=\sum_x 2^x\sum_{i}^{n/x}\sum_j^{n/x}[\gcd(i,j)==1]\\ &=\sum_x^n 2^x\sum_{i}^{n/x}\sum_j^{n/x}\sum_{d|\gcd(i,j)}\mu(d)\\ &=\sum_x^n 2^x\sum_{xd|n}\mu(d)(\frac n{xd})^2\\ &=\sum_T^n(\frac nT)^2\sum_{d|T}2^d\mu(\frac Td)\\ \end{align*} \]

这个显然可以 \(O(n)\) 计算

\((ii)\ ca=cb\ne 0\) ，此时要求 \(S=T\) ，答案 \(\sum 2^i=2^n-2\)

② 若 \(ca\times cb\ge 0\) 且 \(ca\ne cb\) ,\(ca,cb\) 不同时为 \(0\) ，此时显然无解

③ 若 \(ca\times cb<0\) 且 \(ca\ne cb\)，以下令 \(ca=|ca|,cb=|cb|\)

设 \(T=S+X\) ，则 \(ca|S|=cb|S+X|\Rightarrow (ca-cb)|S|=cb|X|\)

此时我们得到了一个子问题，这个子问题一定会到 \(ca^{\prime}=cb^{\prime}=\gcd(ca,cb)\) 的情况

转化成了 \(① (ii)\) 的情况，考虑此时公共循环节长度最大是 $\dfrac n{\frac{\max{ca,cb}}{\gcd(ca,cb)}} $ ，所以答案就是

\[2^{\frac{n}{\max\{\frac{ca}{\gcd(ca,cb)},\frac{cb}{\max(ca,cb)}\}}+1}-2 \]

现在我们来考虑有问号的情况

设 \(A\) 中有 \(p\) 个问号， \(B\) 中有 \(q\) 个问号，我们直接暴力枚举 \(A\) 中有 \(x\) 个问号对应 \(a\) ,\(B\) 中有 \(y\) 个

设 \(f(ca,cb)\) 表示不考虑问号时的答案，\(ca,cb\) 对应不考虑问号时候的值（上面那个式子），那么

\[ans=\sum_{x}^p\sum_y^qf(ca+x-y,cb+p-q-x+y)\binom px\binom qy \]

容易发现仅和 \(x-y\) 有关，我们考虑直接枚举 \(x-y\)

\[ans=\sum_k f(ca+k,cb+p-q-k)\sum_{y=0}^q\binom{p}{p-k-y}\binom qy \]

然后有一个组合恒等式叫做范德蒙德卷积：

\[\sum_k \binom rk\binom{s}{n-k}=\binom {r+s}n \]

Proof

我们直接从组合意义考虑它，左边的意义是枚举第一组选 \(k\) 人，第二组选 \(n-k\) 人的方案数，右边的意义是两组一同选出 \(n\) 人的总方案数

这样我们干成了这样：

\[ans=\sum_k f(ca+k,cb+p-q-k)\binom{p+q}{p-k} \]

Code

#include
#define int long long
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N = 6e5+5;
const int mod = 1e9+7;

char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){
    int s=0,w=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
    return s*w;
}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod,b>>=1;
    }
    return res;
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void inc(int&a,int b){a=a+b>=mod?a-mod+b:a+b;}
void dec(int&a,int b){a=a>=b?a-b:a+mod-b;}

char a[N],b[N];
int prime[N],mu[N],pw[N],jc[N],invj[N],f[N];
int n,cnt,ans;
bool vis[N];

void preparation(){
    mu[1]=1;
    for(int i=pw[0]=jc[0]=1;i=0&&m>=0)return 0;
    if(n<=0&&m<=0)return 0;
    n=abs(n),m=abs(m);
    if(n==m)return pw[::n+1]-2;
    int g=gcd(n,m);
    return pw[(::n)/max(n/g,m/g)+1]-2;
}

signed main(){
    scanf("%s%s",a+1,b+1),n=read(),preparation();
    int lena=strlen(a+1),lenb=strlen(b+1),p=0,q=0,ca=0,cb=0;
    for(int i=1;i<=lena;++i)p+=a[i]=='?',ca+=a[i]=='A',cb+=a[i]=='B';
    for(int i=1;i<=lenb;++i)q+=b[i]=='?',ca-=b[i]=='A',cb-=b[i]=='B';
    for(int i=-max(p,q);i<=max(p,q);++i)if(C(p+q,p-i))
        inc(ans,C(p+q,p-i)*F(ca+i,cb+p-q-i)%mod);
    if(lena==lenb){
        for(int i=1;i<=lena;++i)
            if(a[i]!=b[i]&&a[i]!='?'&&b[i]!='?')
                return printf("%lld\n",ans),0;
        int tmp=1;
        for(int i=1;i<=lena;++i)
            if(a[i]=='?'&&b[i]=='?')
                tmp=tmp*2%mod;
        dec(ans,tmp*f[n]%mod);
        inc(ans,((pw[n+1]-2)*(pw[n+1]-2ll)%mod)*tmp%mod);
    }
    printf("%lld\n",ans);
    return 0;
}