Problem F: Vocabulary
According to a popular belief, computer programmers drink a lot of coffee and know only
a few words. The vocabulary of a typical programmer consists of just three words. Besides, he
rarely knows how to spell them. To help programmers with their spelling mistakes, we published
a book titled The Dictionary of the Three Words Every Typical Programmer Should Know.
You got a copy of the book but, soon after that, you spilled your coffee over it. Now, you
cannot read some of the characters. Fortunately, the three words were, as usually in dictionaries,
distinct and printed in lexicographical order.
Before you attempt to use that fact to recover the missing characters, you want to know in
how many different ways you can do it. Since you expect this number might be large, you want
to know it modulo 109 + 9.
Input
The first line of input contains the number of test cases . The descriptions of the test cases
follow:
Each test case consists of three lines, each containing a single nonempty word – in the order
they appear in the dictionary. Words consist of small letters of the English alphabet and question
marks, the latter denoting missing characters. Each word is at most 1 000 000 characters long.
Output
For each test case, output one line containing the number of different ways you can substitute
each question mark with one of the 26 letters from a to z in such a way that the three words are
distinct and in lexicographical order. The number should be printed modulo 109 + 9.
Example
For an example input the correct answer is:
input:
3
?heoret?cal
c?mputer
?cience
jagiellonian
?niversity
kra?ow
?
b
c
output
42562
52
1
输入和输出：
每组输入有三行，条件是保证三组数据是按照字典序升序排列，？代表可以是任意字母，求满足要求的字符串一共有多少种
做法：dp 难点在于转移方程 ，这里通过写一个函数judge跑了27*27*27*3*3（包含一个最小字符0小于所有字母）
的暴力，预处理出a，b, c字符串中任意字母 和中间两个任意符号的情况数，其实主要是处理带问号的情况
接着就是转移方程，以这一句为例
g[ii][1]=(int)((1LL*g[ii][1]+1LL*g[i][4]*f[0][0][C(a[ii],la,ii)][C(b[ii],lb,ii)][C(c[ii],lc,ii)])%MOD);//4->1 < < 其中 g[i][j]为到第i位,满足j情况的方案数 //三个串的字母与符号: //第一种情况 : x < y < z //第二种情况 : x < y = z //第三种情况 : x = y < z //第四种情况 : x = y = z C 函数用于把字母转成数字和处理长度不够的情况 ii，为当情况前，i为上一种情况，从4转到1，由于上一种情况= = ，现在要转移成为 < <; 所以要用到f[0][0][a[ii]][b[ii]][c[ii]]的情况数，即下一种字母排序也必须是< <才可以， 其他情况分析同上code:
#include<bits/stdc++.h>
#define MOD 1000000009
#define LL long long
#define MAXN 1000010
using namespace std;
int f[3][3][28][28][28],g[MAXN][5];
char a[MAXN],b[MAXN],c[MAXN];
//f[i][j][x][y][z]为当前第一个符号为i(0,1,2分别为<,=,any),第二个符号为j,
bool Judge(int i,int j,int x,int y,int z)
//判断x,y,z是否满足i,j符号的限制
{
if(i==0&&j==0&&x<y&&y<z)return true;
if(i==0&&j==1&&x<y&&y==z)return true;
if(i==0&&j==2&&x<y)return true;
if(i==1&&j==0&&x==y&&y<z)return true;
if(i==1&&j==1&&x==y&&y==z)return true;
if(i==1&&j==2&&x==y)return true;
if(i==2&&j==0&&y<z)return true;
if(i==2&&j==1&&y==z)return true;
if(i==2&&j==2)return true;
return false;
}
int C(char ch,int len,int i)
{
if(i>len)return 0;
if(ch=='?')return 27;
else return ch-'a'+1;
}
int main()
{
//freopen("bzoj4043.in","r",stdin); //freopen("bzoj4043.out","w",stdout);
int i,j,x,y,z,xx,yy,zz,lx,rx,ly,ry,lz,rz,n,la,lb,lc,m,ii;
//f[i][j][x][y][z]为当前第一个符号为i(0,1,2分别为<,=,any),第二个符号为j,
//第一个字母为x(0~27,0为补上的字符,1~26为'a'~'z',
//27为'?'),第二个字母为y,第三个字母为z的方案数
for(i=0; i<=2; i++)
{
for(j=0; j<=2; j++)
{
for(x=0; x<=27; x++)
{
for(y=0; y<=27; y++)
{
for(z=0; z<=27; z++)
{
if(x==0)lx=0,rx=0;
else if(x==27)lx=1,rx=26;
else lx=x,rx=x;
if(y==0)ly=0,ry=0;
else if(y==27)ly=1,ry=26;
else ly=y,ry=y;
if(z==0)lz=0,rz=0;
else if(z==27)lz=1,rz=26;
else lz=z,rz=z;
for(xx=lx; xx<=rx; xx++)
{
for(yy=ly; yy<=ry; yy++)
{
for(zz=lz; zz<=rz; zz++)
{
if(Judge(i,j,xx,yy,zz)==true)f[i][j][x][y][z]++;
}
}
}
}
}
}
}
}
scanf("%d",&n);
//三个串的字母与符号:
//第一种情况 : x < y < z
//第二种情况 : x < y = z
//第三种情况 : x = y < z
//第四种情况 : x = y = z
while(n--)
{
scanf("\n%s\n%s\n%s",a+1,b+1,c+1);
la=strlen(a+1);
lb=strlen(b+1);
lc=strlen(c+1);
m=max(la,max(lb,lc));
//g[i][j]为到第i位,满足j情况的方案数
g[0][4]=1;
for(i=0; i<m; i++) //前一位为i
{
//0,1,2分别为<,=,any
ii=i+1;
g[ii][1]=(int)((1LL*g[ii][1]+1LL*g[i][4]*f[0][0][C(a[ii],la,ii)][C(b[ii],lb,ii)][C(c[ii],lc,ii)])%MOD);//4->1 < <
g[ii][2]=(int)((1LL*g[ii][2]+1LL*g[i][4]*f[0][1][C(a[ii],la,ii)][C(b[ii],lb,ii)][C(c[ii],lc,ii)])%MOD);//4->2 < =
g[ii][3]=(int)((1LL*g[ii][3]+1LL*g[i][4]*f[1][0][C(a[ii],la,ii)][C(b[ii],lb,ii)][C(c[ii],lc,ii)])%MOD);//4->3 = <
g[ii][4]=(int)((1LL*g[ii][4]+1LL*g[i][4]*f[1][1][C(a[ii],la,ii)][C(b[ii],lb,ii)][C(c[ii],lc,ii)])%MOD);//4->4 = =
g[ii][1]=(int)((1LL*g[ii][1]+1LL*g[i][3]*f[0][2][C(a[ii],la,ii)][C(b[ii],lb,ii)][C(c[ii],lc,ii)])%MOD);//3->1 < any
g[ii][3]=(int)((1LL*g[ii][3]+1LL*g[i][3]*f[1][2][C(a[ii],la,ii)][C(b[ii],lb,ii)][C(c[ii],lc,ii)])%MOD);//3->3 = any
g[ii][1]=(int)((1LL*g[ii][1]+1LL*g[i][2]*f[2][0][C(a[ii],la,ii)][C(b[ii],lb,ii)][C(c[ii],lc,ii)])%MOD);//2->1 any <
g[ii][2]=(int)((1LL*g[ii][2]+1LL*g[i][2]*f[2][1][C(a[ii],la,ii)][C(b[ii],lb,ii)][C(c[ii],lc,ii)])%MOD);//2->2 any =
g[ii][1]=(int)((1LL*g[ii][1]+1LL*g[i][1]*f[2][2][C(a[ii],la,ii)][C(b[ii],lb,ii)][C(c[ii],lc,ii)])%MOD);//1->1 any any
}
printf("%d\n",(g[m][1]%MOD+MOD)%MOD);
for(i=0; i<=m; i++)for(j=1; j<=4; j++)g[i][j]=0;
}
return 0;
}简化版代码： 首先我们把所有串变成一样长,不足的位置补'a'-1即可。
设f[i][0]表示对于前i个字符,三个串字典序相等的方案数。
f[i][1]表示对于前i个字符,前两个串的字典序相等并且小于第三个串的方案数。
f[i][2]表示对于前i个字符,后两个串的字典序相等并且大于第一个串的方案数。
f[i][3]表示对于前i个字符,三个串字典序各不相同并且从小到大排序的方案数。
这样转移显然非常麻烦。
我们考虑预处理。
设g[i][j][x][y][z]表示上一个状态是i,当前三个串的字符分别是x,y,z,转移到状态j的方案数。
这个东西暴力枚举所有情况即可。
然后f数组就很好求了。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1000010
#define P 1000000009
using namespace std;
int T,n,len,a[N],b[N],c[N],n1,n2,n3;
long long g[4][4][28][28][28],f[N][4];
char s1[N],s2[N],s3[N];
void pre(){
int i,j,k,l1,r1,l2,r2,l3,r3,x,y,z;
for (i=0;i<=27;i++)
for (j=0;j<=27;j++)
for (k=0;k<=27;k++){
if (i==27){l1=1;r1=26;}else{l1=i;r1=i;}
for (x=l1;x<=r1;x++){
if (j==27){l2=1;r2=26;}else{l2=j;r2=j;}
for (y=l2;y<=r2;y++){
if (k==27){l3=1;r3=26;}else{l3=k;r3=k;}
for (int z=l3;z<=r3;z++){
if (x==y&&y==z) g[0][0][i][j][k]++;
if (x==y&&y<z)g[0][1][i][j][k]++;
if (x<y&&y==z)g[0][2][i][j][k]++;
if (x<y&&y<z) g[0][3][i][j][k]++;
if (x==y) g[1][1][i][j][k]++;
if (x<y) g[1][3][i][j][k]++;
if (y==z) g[2][2][i][j][k]++;
if (y<z) g[2][3][i][j][k]++;
g[3][3][i][j][k]++;
}
}
}
}
}
void work(char *s,int *a,int n){
for(int i=0;i<n;i++) if (s[i]=='?') a[i+1]=27;else a[i+1]=s[i]-'a'+1;
for (int i=n;i<len;i++) a[i+1]=0;
}
int main(){
pre();scanf("%d",&T);
while (T--){
scanf("%s",s1);scanf("%s",s2);scanf("%s",s3);
n1=strlen(s1);n2=strlen(s2);n3=strlen(s3);len=max(max(n1,n2),n3);
work(s1,a,n1);work(s2,b,n2);work(s3,c,n3);
f[0][0]=1;
for (int i=1;i<=len;i++){
f[i][0]=f[i][1]=f[i][2]=f[i][3]=0;
for (int j=0;j<4;j++)
for (int k=0;k<4;k++){
if (f[i-1][k]) (f[i][j]+=f[i-1][k]*g[k][j][a[i]][b[i]][c[i]])%=P;
}
}
printf("%lld\n",f[len][3]);
}
}
京公网安备 11010502036488号