\(\\\)
给出三个长度分别为 \(lenA,lenB,lenC\) 的三个字符串 \(A,B,C\) ，其中字符集只包括所有小写字母以及 \(?\) 号。
现在将所有 \(?\) 号改为任意小写字母，问有多少种方案，使得 \(A,B,C\) 三个字符串按照字典序排列\((\)相同不算\()?\)
输出方案数对 \(10^9+9\) 取模后的结果。多组询问。
- 字符串总长度\(\le 10^6\)
\(\\\)
\(Solution\)
有趣的预处理题目。
三个串长度不能确定，不能通过数据组数判断复杂度要求，只好按照上界分析，即只有一组数据，做法接近线性。
首先考虑三个串不等长的问题，字典序中规定，一个串的任意长度前缀都比当前串字典序小，所以在不是最长的串后面补上若干个比 \(a\) 还要小的字符即可。
\(\\\)
考虑为了使得最后合法，三个串的字典序在确定 \(?\) 号的时候合法的情况（小于号表示字典序左侧优于右侧）：
- \(1:\ A=B=C\)
- \(2:\ A<B=C\)
- \(3:\ A=B<C\)
- \(4:\ A<B<C\)
其他情况会导致在某一位置某两串字典序相反，这样后面不管怎样设置字典序都是反过来的。
\(\\\)
动态规划。
设\(f[i][1/2/3/4]\)表示，当前位置为\(i\)，当前位置及以前的所有 \(?\) 号都确定完了之后，使得三个串的字典序关系变为 \(1/2/3/4\) 的方案数。
为了便于初始化，将字符串都向后推一个，然后有\(f[0][1]=1\)，答案为\(f[maxlen][4]\)。
考虑转移的过程，合法的转移有：\(1 \to 1/2/3/4\ ,\ 2\to 2/4\ ,\ 3\to 3/4\ ,\ 4\to4\)，想不明白可以手玩一下，当前位置每一种情况的字典序的前提是不同的，例如 \(1\) 类情况必须要求前面的位置都为 \(1\) 类情况。
\(\\\)
然后考虑转移的过程，显然我们的转移影响要素有，前一位置状态，以及当前位置三个字符串的字符。
考虑到每次操作统计方案数非常麻烦，而转移只有 \(28^3\times(4+2+2+1)\) 种\((\)后面括号里对应着状态间的转移\()\)，不妨对每个转移处理出来方案数。
设 \(g[i][j][x][y][z]\) 表示，要从状态 \(i\) 转移到 \(j\) ，当前位置三个串的字符分别为 \(x,y,z\) 的方案数，预处理就暴力枚举三个字符，注意从上到下字符区间的限制，然后将可以累加的转移方案数累加就好。
然后我们动规的转移就可以直接借用 \(g\) 数组转移了，单组数据复杂度 \(\text O (16N)\)。
\(\\\)
\(Code\)
#include#include #include #include #include #include #include #define N 1000010#define R register#define mod 1000000009using namespace std;typedef long long ll;char a[N],b[N],c[N]; ll f[N][4],g[4][4][28][28][28]; int s1[N],s2[N],s3[N],lena,lenb,lenc,len; inline void prework(){ int l1,r1,l2,r2,l3,r3; for(R int i=0;i<=27;++i) for(R int j=0;j<=27;++j) for(R int k=0;k<=27;++k){ (i==27)?l1=1,r1=26:l1=r1=i; for(R int x=l1;x<=r1;++x){ (j==27)?l2=1,r2=26:l2=r2=j; for(R int y=l2;y<=r2;++y){ (k==27)?l3=1,r3=26:l3=r3=k; for(R int z=l3;z<=r3;++z){ ++g[3][3][i][j][k]; if(x==y) ++g[1][1][i][j][k]; if(x