The problem requires selecting names of lengths from 1 to N, where each name in a given layer must be formed by adding a single character to the beginning or end of a name from the previous layer. This can be efficient solved using string hashing and dynamic programming.

Approach

We can compute three hash values for each name:

• The full hash of the entire string.
• The hash of the string with the first character removed.
• The hash of the string with the last character removed.

These hashes allow us to compare a name in the current layer with names in the previous layer to check if it can be formed by adding a character to either end. We then use dynamic programming to count the number of valid sequences.

Complexity

This approach has a time complexity of O(N * K^2), which is acceptable given the constraints (N ≤ 50, K ≤ 1500).

Implementation

We use a rolling hash with a base of 1145141 and store DP states for each name in each layer.

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAX_N = 51, MAX_K = 1600, MOD = 1e9 + 7;
const unsigned long long BASE = 1145141;

int n, k;
int dp[MAX_N][MAX_K];
unsigned long long hashVals[MAX_N][MAX_K][3];

unsigned long long computeHash(const char* str, int start, int end) {
    unsigned long long result = 0;
    for (int i = start; i < end; i++) {
        result = result * BASE + (str[i] - 'a' + 1);
    }
    return result;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    char buffer[MAX_K];

    // Initialize first layer
    for (int i = 0; i < k; i++) {
        cin >> buffer;
        int len = strlen(buffer);
        hashVals[0][i][2] = computeHash(buffer, 0, len);
        dp[0][i] = 1;
    }

    // Process subsequent layers
    for (int layer = 1; layer < n; layer++) {
        for (int idx = 0; idx < k; idx++) {
            cin >> buffer;
            int len = strlen(buffer);
            hashVals[layer][idx][0] = computeHash(buffer, 0, len - 1);
            hashVals[layer][idx][1] = computeHash(buffer, 1, len);
            hashVals[layer][idx][2] = computeHash(buffer, 0, len);
        }

        // Update DP for current layer
        for (int curr = 0; curr < k; curr++) {
            dp[layer][curr] = 0;
            for (int prev = 0; prev < k; prev++) {
                if (hashVals[layer][curr][0] == hashVals[layer - 1][prev][2] ||
                    hashVals[layer][curr][1] == hashVals[layer - 1][prev][2]) {
                    dp[layer][curr] = (dp[layer][curr] + dp[layer - 1][prev]) % MOD;
                }
            }
        }
    }

    // Sum results for the last layer
    int total = 0;
    for (int i = 0; i < k; i++) {
        total = (total + dp[n - 1][i]) % MOD;
    }
    cout << total << endl;

    return 0;
}

Key Points

• The DP array dp[layer][idx] stores the number of valid sequences ending with the idx-th name in the layer-th layer.
• Hashing is performed using a simple polynomial rolling hash.
• The solution avoids storing adjacency lists explicitly to save memory, processing comparisons directly during input reading.