自动搬运

查看原文

来自洛谷，原作者为

	uibn **

搬运于2025-08-24 22:03:20，当前版本为作者最后更新于2021-06-21 21:10:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

三个字符串，设最长的长为 $n$ ，则空格可以看成 $0$ ，$a$ 到 $z$ 分别看成 $1$ 到 $26$ ，$?$ 看成 $-1$ 。

从后到前考虑每一位，符合的有如下四种情况：

$a<b<c$ ，$a<b=c$ ， $a=b<c$ ， $a=b=c$

第一种：答案直接加上 $26$ 的后面 $?$ 个数次方。

第二种、第三种：预处理只有两个字符串时的答案。

第四种：与上一位的答案相同

还要枚举每一位是不是问号，有八种情况。

注意要时刻取模，不然就溢出了。

还有 $26$ 的若干次方提前预处理。

#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;
}