Rafid - Dictionary - DP long

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define fap(x) cout << __LINE__ << " says: " << #x << " = " << (x) << "\n"
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const long long INF = 2000000000000000000LL;    // 2e18
const int inf = 0x3f3f3f3f;
const long double EPS = 1e-9;

const int N = 53;
const int L = 23;
const int A = 26;
const ll MOD = 1000000007LL;
const ll MOD2 = MOD*MOD;

ll dp[L][N][N]; // idx, fr, to
ll aux[N][A+3]; // idx, alphabet

string g[N];    // grid
int front[A+3]; // starting pos of char

int main() {
//    freopen("out.txt", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    for(int i=0; i<n; ++i) cin >> g[i];

    int len = 0;
    for(int i=0; i<n; ++i) len = max(len, (int) g[i].size());
    for(int i=0; i<n; ++i) g[i] += string(len - (int) g[i].size(), 'a'-1);

    for(int fr=0; fr<n; ++fr) {
        dp[len][fr][fr] = 1;
    }

    for(int idx=len-1; idx>=0; --idx) {
        for(int gap=1; gap<=n; ++gap) {
            for(int fr=0, to=fr+gap-1; to<n; ++fr,++to) {
                ll &res = dp[idx][fr][to];
                res = 0;

                if(fr == to) {
                    if(g[fr][idx] == '?') res += dp[idx+1][fr][to] * 26;
                    else res += dp[idx+1][fr][to];
                }
                else {
                    string s = "";
                    for(int i=fr; i<=to; ++i) s += g[i][idx];
                    int sz = (int) s.size();

                    memset(front, inf, sizeof front);
                    for(int i=0; i<sz; ++i) if(islower(s[i])) front[s[i]-'a'] = min(front[s[i]-'a'], i);

//                    cout << "\n";
//                    fap(idx), fap(fr), fap(to), fap(s);
//                    fap("------------------------");

                    for(int i=0; i<=A; ++i) aux[0][i] = 1;
                    // aux[0][0] = 1;
                    for(int i=1; i<=sz; ++i) {
                        bool offset = true;
                        for(int j=0; j<i; ++j) offset &= (s[j] == 'a'-1);
                        aux[i][0] = offset;

                        for(int c=1; c<=A; ++c) {
                            aux[i][c] = aux[i][c-1];

                            bool ok = true;
                            for(int j=front[c-1]; j<i; ++j) {
                                if(s[j] != '?' and s[j]-'a' != c-1) {
                                    ok = false;
                                    break;
                                }
                            }
                            if(!ok) continue;

                            for(int j=min(front[c-1]+1, i); j>0; --j) {
                                if(s[j-1] != '?' and s[j-1]-'a' != c-1) break;
                                aux[i][c] += (dp[idx+1][fr+j-1][fr+i-1] * aux[j-1][c-1]) % MOD;
                                if(aux[i][c] >= MOD2) aux[i][c] -= MOD2;
//                                fap(j), fap(fr+j-1), fap(fr+i-1), fap((char) ('a'+c-1)), fap((dp[idx+1][fr+j-1][fr+i-1] * aux[j-1][c-1]));
//                                fap(j), fap(aux[i][c]), fap(fr+j-1), fap(fr+i-1), fap("meantime-----------------------");
                            }
                            aux[i][c] %= MOD;

//                            fap(i), fap(c), fap(aux[i][c]);
                        }
                    }

                    res = aux[sz][A];
//                    fap(res);
                }

                res %= MOD;
            }
        }
    }

    ll ans = dp[0][0][n-1];
    cout << ans << "\n";

    return 0;
}

/**

3
snuje
????e
snule

2
?sum??mer
c??a??mp

**/