Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <memory.h>
- #include <cstdlib>
- #include <ctime>
- #define forn(i, n) for (int i = 0; i < (int) n; ++i)
- typedef long long ll;
- using namespace std;
- const int MOD = 1e9 + 7;
- const int A = ('z' - 'a' + 1) + 1;
- void add(int& x, int y) {
- ((x += y) >= MOD) && (x -= MOD);
- }
- int mul(int x, int y) {
- return x * 1ll * y % MOD;
- }
- int len = 0;
- char S[60][30];
- int s[60][30];
- int n;
- int dp[55][55][22][30];
- int sum_dp[55][55][22][30];
- bool was_sum[55][55][22];
- int calc(int l, int r, int pos, int c);
- void calc_sum(int l, int r, int pos) {
- if (was_sum[l][r][pos]) {
- return;
- }
- was_sum[l][r][pos] = true;
- int res = 0;
- sum_dp[l][r][pos][0] = 0;
- forn(c, A) {
- add(res, calc(l, r, pos, c));
- sum_dp[l][r][pos][c + 1] = res;
- // add(sum_dp[l][r][pos][c + 1], sum_dp[l][r][pos][c]);
- }
- }
- int calc(int l, int r, int pos, int c) {
- // printf("%d %d %d %d\n", l, r, pos, c);
- if (l > r) {
- return 1;
- }
- int& res = dp[l][r][pos][c];
- if (res != -1) {
- return res;
- }
- res = 0;
- for (int R = l; R <= r; ++R) {
- if (c == A - 1 && s[R][pos] != c) {
- break;
- }
- if (s[R][pos] != A && s[R][pos] != c) {
- break;
- }
- if (pos == len - 1 && R > l) {
- break;
- }
- int cur1 = 0;
- if (pos < len - 1) {
- calc_sum(l, R, pos + 1);
- add(cur1, sum_dp[l][R][pos + 1][A]);
- // for (int nc = 0; nc < A; ++nc) {
- // add(cur1, calc(l, R, pos + 1, nc));
- // }
- } else {
- cur1 = 1;
- }
- int cur2 = 0;
- if (R == r) {
- cur2 = 1;
- } else {
- calc_sum(R + 1, r, pos);
- add(cur2, sum_dp[R + 1][r][pos][A]);
- add(cur2, -sum_dp[R + 1][r][pos][c + 1] + MOD);
- // for (int nc = c + 1; nc < A; ++nc) {
- // add(cur2, calc(R + 1, r, pos, nc));
- // }
- }
- add(res, mul(cur1, cur2));
- }
- return res;
- }
- int main()
- {
- // #define vlad
- #ifdef DEBUG
- freopen("input.txt", "rt", stdin);
- // freopen("output.txt", "w", stdout);
- #endif
- scanf("%d\n", &n);
- forn(i, n) {
- gets(S[i]);
- int cur = strlen(S[i]);
- len = max(len, cur);
- }
- /*
- len = 20;
- n = 50;
- forn(i, n) {
- forn(j, len) {
- s[i][j] = A;//rand() % (A + 1);
- }
- } */
- forn(i, n) {
- forn(j, strlen(S[i])) {
- if (S[i][j] == '?') {
- s[i][j] = A;
- } else {
- s[i][j] = S[i][j] - 'a';
- }
- }
- for (int j = strlen(S[i]); j < len; ++j) {
- s[i][j] = A - 1;
- }
- }
- /*
- printf("len = %d, n = %d\n", len, n);
- forn(i, n) {
- forn(j, len) {
- printf("%3d ", s[i][j]);
- }
- puts("");
- }
- puts("");
- printf("A = %d\n", A);
- */
- memset (dp, -1, sizeof dp);
- // printf("%d\n", s[0][0]);
- // printf("calc = %d\n", calc(0, 1, 0, 1));
- // return 0;
- int res = 0;
- forn(c, A - 1) {
- add(res, calc(0, n - 1, 0, c));
- }
- printf("%d\n", res);
- // printf("%.10f\n", (double) clock() / CLOCKS_PER_SEC);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement