Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<ctime>
- #include<stdio.h>
- #include<string>
- #include<algorithm>
- #include<iostream>
- #include<vector>
- #include<set>
- #include<map>
- #include<queue>
- #include<list>
- #include<memory.h>
- using namespace std;
- typedef long long ll;
- typedef vector<int> vi;
- typedef long double ld;
- typedef pair<int, int> pii;
- typedef pair<ll, ll> pll;
- const int inf = 1e9+7;
- const ld eps = 1e-16;
- int n;
- char a[55][22], len[55];
- int f[22][55][55][30];
- bool marked[22][55][55][30];
- int maxLen[55][55];
- int qc[22][55][55];
- int rec(int c, int l, int r, char maxQ){
- if(r < l)
- return 1;
- if(c >= maxLen[l][r])
- return 0;
- if(marked[c][l][r][maxQ])
- return f[c][l][r][maxQ];
- marked[c][l][r][maxQ] = true;
- if(l == r){
- if(c > len[l]){
- return f[c][l][r][maxQ] = 0;
- }else{
- ll q = 1;
- for(int i = c; i < len[l]; i++){
- if(a[l][i] == '?'){
- q = (q * maxQ) % inf;
- maxQ = 26;
- }else if(a[l][i] - 'a' < maxQ){
- maxQ = 26;
- }
- }
- return f[c][l][r][maxQ] = q;
- }
- }
- int res = 0;
- int minQ = -1;
- for(int i = l; i <= r; i++){
- char w = qc[c][i][r];
- if(w == 1)
- continue;
- if(w != '?' && w - 'a' <= minQ)
- continue;
- if(a[i][c] != '?' && a[i][c] - 'a' > minQ){
- minQ = a[i][c] - 'a';
- }
- if(w == '?'){
- for(int q = minQ + 1; q < maxQ; q++){
- res += ((ll)rec(c + 1, i, r, 26) * rec(c, l, i - 1, q)) % inf;
- if(res > inf)
- res -= inf;
- }
- }else if(w - 'a' < maxQ){
- res += ((ll)rec(c + 1, i, r, 26) * rec(c, l, i - 1, w - 'a')) % inf;
- if(res > inf)
- res -= inf;
- }
- }
- return f[c][l][r][maxQ] = res;
- }
- int main(){
- #ifdef _BSUIR2JUDGE_
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- //freopen("sum.in", "r", stdin);
- //freopen("sum.out", "w", stdout);
- #endif
- memset(a, 0, sizeof(a));
- scanf("%d\n", &n);
- for(int i = 0; i < n; i++){
- scanf("%s\n", &a[i][0]);
- len[i] = strlen(a[i]);
- }
- for(int i = 0; i < n; i++){
- int ml = 0;
- for(int j = i; j < n; j++){
- ml = max(ml, (int)len[j]);
- maxLen[i][j] = ml;
- }
- }
- for(int k = 0; k < 22; k++){
- for(int i = 0; i < n; i++){
- char w = '?';
- for(int j = i; j < n; j++){
- if(w != 1){
- if(a[j][k] != '?' && w != '?' && a[j][k] != w){
- w = 1;
- }else if(a[j][k] != '?'){
- w = a[j][k];
- }
- }
- qc[k][i][j] = w;
- }
- }
- }
- cout << rec(0, 0, n - 1, 26);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement