P4761
三个字符串，设最长的长为
从后到前考虑每一位，符合的有如下四种情况：
第一种：答案直接加上
第二种、第三种：预处理只有两个字符串时的答案。
第四种：与上一位的答案相同
还要枚举每一位是不是问号，有八种情况。
注意要时刻取模，不然就溢出了。
还有
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
char ch[1000005];
void Read(int *a,int &n)
{
scanf("%s",ch+1);
for (n=1;ch[n]!='\0';n++) ; n--;
for (int i=1;i<=n;i++) a[i]=(ch[i]=='?')?-1:ch[i]-'a'+1;
for (int i=1;i<=n;i++) ch[i]='\0';
}
const long long M=1e9+9;
long long Mit[4000001];
long long Mi(long long a,long long b)
{
if (a==26) return Mit[b];
}
void Calc(long long *f,int n,int *a,int *b)
{
int ca=0,cb=0;
if (a[n]!=-1&&b[n]!=-1)
{
if (a[n]>=b[n]) f[n]=0;
else f[n]=1;
}
else if (a[n]!=-1) f[n]=26-a[n];
else if (b[n]!=-1) f[n]=b[n]-1;
else f[n]=13*25;
if (a[n]==-1) ca++;
if (b[n]==-1) cb++;
for (int i=n-1;i>=1;i--)
{
if (a[i]!=-1&&b[i]!=-1)
{
if (a[i]>b[i]) f[i]=0;
else if (a[i]<b[i]) f[i]=Mi(26,ca+cb);//
else f[i]=f[i+1];
}
else if (a[i]!=-1)
{
f[i]=1ll*(26-a[i])*Mi(26,ca+cb)%M+f[i+1];
if (f[i]>=M) f[i]-=M;
}
else if (b[i]!=-1)
{
f[i]=1ll*(b[i]-1)*Mi(26,ca+cb)%M+f[i+1];
if (f[i]>=M) f[i]-=M;
}
else
{
f[i]=13ll*25ll*Mi(26,ca+cb)%M+26ll*f[i+1]%M;
if (f[i]>=M) f[i]-=M;
}
if (a[i]==-1) ca++;
if (b[i]==-1) cb++;
}
}
int T,n;
int a[1000005],b[1000005],c[1000005];
int la,lb,lc;
long long g1[1000005],g2[1000005],f[1000005];
int main()
{
Mit[0]=1ll;
for (int i=1;i<=3000000;i++) Mit[i]=Mit[i-1]*26ll%M;//预处理26的若干次方结果
scanf("%d",&T);
while (T--)
{
Read(a,la),Read(b,lb),Read(c,lc);//读入时从字符转为数字
n=max(la,max(lb,lc));
Calc(g1,n,a,b);//预处理只考虑a,b的情况
Calc(g2,n,b,c);//预处理只考虑b,c的情况
// for (int i=1;i<=n;i++) printf("%d %d %d\n",i,g1[i],g2[i]);
int ca=0,cb=0,cc=0;//计算问号数目//注意第n位要严格不相等
if (a[n]!=-1&&b[n]!=-1&&c[n]!=-1)
{
if (a[n]<b[n]&&b[n]<c[n]) f[n]=1;
else f[n]=0;
}
else if (a[n]!=-1&&b[n]!=-1)
{
if (a[n]<b[n]) f[n]=26-b[n];
else f[n]=0;
}
else if (a[n]!=-1&&c[n]!=-1)
{
if (a[n]+1<c[n]) f[n]=c[n]-a[n]-1;
else f[n]=0;
}
else if (b[n]!=-1&&c[n]!=-1)
{
if (b[n]<c[n]) f[n]=b[n]-1;
else f[n]=0;
}
else if (a[n]!=-1)
{
f[n]=1ll*(26-a[n])*(26-a[n]-1)/2;
}
else if (b[n]!=-1)
{
f[n]=1ll*(b[n]-1)*(26-b[n]);
}
else if (c[n]!=-1)
{
f[n]=1ll*(c[n]-1)*(c[n]-2)/2;
}
else
{
f[n]=1ll*26*25*24/6;
}
if (a[n]==-1) ca++;
if (b[n]==-1) cb++;
if (c[n]==-1) cc++;
f[n]%=M;
for (int i=n-1;i>=1;i--)
{
if (a[i]!=-1&&b[i]!=-1&&c[i]!=-1)
{
if (a[i]<b[i]&&b[i]<c[i]) f[i]=Mi(26,ca+cb+cc);
else if (a[i]<b[i]&&b[i]==c[i]) f[i]=Mi(26,ca)*g2[i+1]%M;
else if (a[i]==b[i]&&b[i]<c[i]) f[i]=Mi(26,cc)*g1[i+1]%M;
else if (a[i]==b[i]&&b[i]==c[i]) f[i]=f[i+1];
else f[i]=0;
}
else if (a[i]!=-1&&b[i]!=-1)
{
if (a[i]<b[i]) f[i]=1ll*(26-b[i])*Mi(26,ca+cb+cc)%M+1ll*Mi(26,ca)*g2[i+1]%M;
else if (a[i]==b[i]) f[i]=1ll*(26-b[i])*g1[i+1]%M*Mi(26,cc)%M+f[i+1];
else f[i]=0;
}
else if (a[i]!=-1&&c[i]!=-1)
{
if (a[i]<c[i]) f[i]=1ll*(c[i]-a[i]-1)*Mi(26,ca+cb+cc)%M+1ll*Mi(26,cc)*g1[i+1]%M+1ll*Mi(26,ca)*g2[i+1]%M;
else if (a[i]==c[i]) f[i]=f[i+1];
else f[i]=0;
}
else if (b[i]!=-1&&c[i]!=-1)
{
if (b[i]<c[i]) f[i]=1ll*(b[i]-1)*Mi(26,ca+cb+cc)%M+1ll*Mi(26,cc)*g1[i+1]%M;
else if (b[i]==c[i]) f[i]=1ll*(b[i]-1)*g2[i+1]%M*Mi(26,ca)%M+f[i+1];
else f[i]=0;
}
else if (a[i]!=-1)
{
f[i]=1ll*(26-a[i])*(26-a[i]-1)/2%M*Mi(26,ca+cb+cc)%M+Mi(26,ca)*g2[i+1]%M*(26-a[i])%M+
Mi(26,cc)*g1[i+1]%M*(26-a[i])%M+f[i+1];
}
else if (b[i]!=-1)
{
f[i]=1ll*(b[i]-1)*(26-b[i])%M*Mi(26,ca+cb+cc)%M+Mi(26,ca)*g2[i+1]%M*(b[i]-1)%M+
Mi(26,cc)*g1[i+1]%M*(26-b[i])%M+f[i+1];
}
else if (c[i]!=-1)
{
f[i]=1ll*(c[i]-1)*(c[i]-2)/2%M*Mi(26,ca+cb+cc)%M+Mi(26,ca)*g2[i+1]%M*(c[i]-1)%M+
Mi(26,cc)*g1[i+1]%M*(c[i]-1)%M+f[i+1];
}
else
{
f[i]=1ll*26*25*24/6*Mi(26,ca+cb+cc)%M+Mi(26,ca)*g2[i+1]%M*13ll*25ll%M+
Mi(26,cc)*g1[i+1]%M*13*25%M+1ll*26*f[i+1]%M;
}
if (a[i]==-1) ca++;
if (b[i]==-1) cb++;
if (c[i]==-1) cc++;
f[i]%=M;
}
printf("%lld\n",f[1]);
for (int i=1;i<=la;i++) a[i]=0;
for (int i=1;i<=lb;i++) b[i]=0;
for (int i=1;i<=lc;i++) c[i]=0;
}
return 0;
}