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