是之前 XJ 搬过的题，不过我那次听得云里雾里没去订。
先考虑没有问号的做法。
Part 1 全部相等时的计算
对于 (A,B) 可以自己上下对应的两个串，必定是所有替换都是合法的，只要满足长度限制的串全都是合法的，这个很好判断，并且答案就是两个独立方案的乘积。具体的，是 ((sum_{i=1}^nlimits 2^i)^2)。
那么对于剩下的情况，必然存在某两个字母替换成 (01) 串后有交的部分，每个相交都对应着某段前缀与后缀的匹配。
Part 2 证明 (A) 和 (B) 都可以表示成另一个串的重复出现若干次的形式。
并且，基于某一步贪心，必定可以将原状态消成一个状态，头尾都满足：两个串的其中一个是 (A)，另一个是 (B)。
那么这样，(A,B) 中必然有一个是另一个的前缀，并且是后缀。
然后呢？
冷静头脑.jpg
放弃思考.jpg
等等，既然可以这么消 (cdots)
钦定 (|A|ge |B|)，然后 (A-B) 这个新串，下一步会匹配 (A) 或者 (B)，但不管是哪一个 (A-B) 的前缀一定是 (B)，除非它的长度小于 (B)。
而小于的情况则表明：(A-B) 是 (B) 的一段前缀。
先不考虑最后的那一步不够的情况，对于前面的，如果一直往后匹配到一个 (A)，那么会出现：
BB____
BB____
那么就可以把 (A) 表示成若干个 (B) 加上一段 (B) 的前缀的形式。
那么现在就只剩下了两个串 (B) 和 (B) 的某一段前缀。
而另一种情况，你会发现，也是符合这个情况的。
在这么不停地转换之后，你会发现：这个过程非常类似求 (gcd)，一直到留下的两个串长度为倍数关系的时候，才会停止，并且此时所有串都可以表现成一种形式。
按照这个过程，我们可以将 (A) 串 和 (B) 串都拆开，拆分成若干段相同的东西。它们两个串都是这个东西的不断重复。
并且依据这个过程，我们发现两个串长度的关系就是在求 (gcd) 的过程。
所以我们证明了标题，并且知道这个公共串 (C) 的长度就是 (gcd(|A|,|B|))。
Part 3 剩余部分的答案计算
那么 (A) 和 (B) 的顺序自然就无所谓了，我们需要在意的只有个数。
(A) 和 (B) 所拥有的重复的串 (C) 的个数必须满足：(num_A cdot S_A +num_B cdot S_B) 这个东西上下相同（(num) 表示这个字母的个数，(S) 表示每个这个字母转化成 (C) 的个数）。
又发现这样考虑的话影响答案的是上下相差的 (A,B) 个数。
定义 (a=) 上面的 (A) 的个数减去下面的 (A) 的个数，(b) 的定义等价,不过是下减上。
(a,b) 若异号则直接无解。
那么 (acdot |A|=bcdot |B|)，并且 (|C|=gcd(|A|,|B|))
若 (a,b) 都为 (0)，那么我们可以将上下看做同构，那么答案为：
这个东西非常好做，你可以整除分块，也就是我写的 (operatorname O(n)) 的，暴力是 (operatorname O(nlog n))，差别不大。
然后考虑 (a,b) 不为 (0) 的情况（其中一个为 (0) 无解）。我们可以先将 (a,b) 变成 (frac{a}{gcd(a,b)},frac{b}{gcd(a,b)})，这样的话限制是等价的。那么此时 (a,b) 就已经互质了。
考虑上面那个式子，我们可以得到：(frac{|B|}{gcd(|A|,|B|)}=a,frac{|A|}{gcd(|A|,|B|)}=b)。
设 (Ed=lfloorfrac{n}{max(a,b)} floor) 那么答案的计算就是：
接下去，我们考虑怎么去考虑有问号的情况。
对于每一组 (a,b)，根据上面的分析，它们的答案有三种情况，我们定义 (f_{a,b}) 表示这个东西：
-
(ab>0) 时，是一个二的幂次的前缀和，即为 (sum_{i=1}^{lfloorfrac{n}{max(a,b) floor}}limits 2^i)。
-
(a=b=0) 时，定义为前面所讲的同构的那个式子，莫反处理出来的那个。
-
然后，在第二种情况下，有一小部分比较特殊，它们上下完全相同，此时的方案计算又要用到第一个式子，就是 ((sum_{i=1}^nlimits 2^i)^2)。
(a,b) 的定义照旧，不过新增两个变量 (x,y) 分别表示上面和下面的问号数量。
那么答案就可以表示为：
惊奇地发现 (f) 这一项只和 (i-j) 有关。
大致是这样的感觉，后面部分可以容斥然后范雷蒙德卷积搞成两个组合数的差。
具体的 (j) 的范围，还取决于枚举的 (i-j) 的大小。
这里考虑到，由于 (j) 的范围不合法只会使得一些照理来说定义为 (0) 的组合数 (inom{x}{k+j}) 出现，而我刚刚因为将其当做未定义，会使得答案无法计算。
实际应该是可以直接将 (j) 的枚举范围改为 ([0,y]) 的，然后范德蒙德卷积卷起来，也就是：(inom{x+y}{k+y})。
那么就做完了。
Part 4 Code
#include <vector>
#include <string>
#include <stdio.h>
#include <iostream>
#define LL long long
using namespace std;
inline LL rin()
{
LL s=0;
bool bj=false;
char c=getchar();
for(;(c>'9'||c<'0')&&c!='-';c=getchar());
if(c=='-')bj=true,c=getchar();
for(;c>='0'&&c<='9';c=getchar())s=(s<<1)+(s<<3)+(c^'0');
if(bj)return -s;
return s;
}
const int N=6e5+3;
const int M=1e9+7;
inline int prpr(int x,int y){return 1LL*x*y%M;}
inline int ksm(int x,int y){int ans=1;for(;y;y>>=1){if(y&1)ans=prpr(ans,x);x=prpr(x,x);}return ans;}
int pw[N];
int sl[N];
int sr[N];
int mu[N];
bool pri[N];
vector<int>prime;
int Gura_do_not_know_my_exist;
int CS[N];
inline int cs(int n)
{
if(CS[n])return CS[n];
int ans=0;
for(int l=1,r,nw;l<=n;l=r+1)r=n/(nw=n/l),ans=(ans+prpr(mu[r]-mu[l-1],prpr(nw,nw)))%M;
return CS[n]=ans;
}
inline void init(int n)
{
pw[0]=1;for(int i=1;i<N;i++)pw[i]=(pw[i-1]<<1)%M;
pw[0]=0;for(int i=2;i<N;i++)pw[i]=(pw[i-1]+pw[i])%M;
sl[0]=1;for(int i=1;i<N;i++)sl[i]=prpr(sl[i-1],i);sr[N-1]=ksm(sl[N-1],M-2);
sr[0]=1;for(int i=N-2;i>=1;i--)sr[i]=prpr(sr[i+1],i+1);
mu[1]=1;
for(int i=2,now;i<N;i++)
{
if(!pri[i])prime.push_back(i),mu[i]=-1;
for(vector<int>::iterator j=prime.begin();j!=prime.end();j++){if((now=(*j)*i)>=N)break;pri[now]=true;if(i%(*j)==0)break;mu[now]=-mu[i];}
mu[i]+=mu[i-1];
}
for(int l=1,r,nw;l<=n;l=r+1)
{
r=n/(nw=n/l);
Gura_do_not_know_my_exist+=prpr(pw[r]-pw[l-1],cs(nw));
Gura_do_not_know_my_exist%=M;
}
return;
}
inline int C(int a,int b){return (a<b||b<0)?(0):(prpr(sl[a],prpr(sr[b],sr[a-b])));}
inline int Gcd(int a,int b){return (!b)?(a):(Gcd(b,a%b));}
int n;
int ans;
string S,T;
inline void work(int i,int a,int b,int x,int y)
{
a+=i;b+=i;
if(!a&&!b){ans=(ans+prpr(Gura_do_not_know_my_exist,C(x+y,i+y)))%M;return;}
if((1LL*a*b)<=0)return;
int c=Gcd(a,b);a/=c;b/=c;
ans=(ans+prpr(pw[n/max(a,b)],C(x+y,i+y)))%M;
return;
}
inline bool check(int s,int t)
{
if(s!=t)return false;for(int i=0;i<s;i++)if(S[i]!=T[i]||S[i]=='?'||T[i]=='?')return false;
printf("%d
",prpr(pw[n],pw[n]));return true;
}
int main()
{
int s,t,a,b,x,y;a=b=x=y=0;
cin>>S>>T;s=S.length();t=T.length();n=rin();init(n);
if(check(s,t))return 0;
for(int i=0;i<s;i++){if(S[i]=='A')a++;if(S[i]=='B')b--;if(S[i]=='?')x++;}
for(int i=0;i<t;i++){if(T[i]=='A')a--;if(T[i]=='B')b++;if(T[i]=='?')y++;}
for(int i=-y;i<=x;i++)work(i,a,b+y-x,x,y);
if(s==t)
{
int cut=1;
for(int i=0;i<s;i++)
{
if(S[i]=='?'&&T[i]=='?'){cut=(cut<<1)%M;continue;}
if(S[i]=='?'||T[i]=='?'||S[i]==T[i])continue;
cut=0;break;
}
ans=(ans+prpr(prpr(pw[n],pw[n])-Gura_do_not_know_my_exist,cut))%M;
ans=(ans+M)%M;
}
printf("%d
",ans);
return 0;
}