Cerinta completa

String is called a Super String if and only if:

  • contains only letters ;
  • For any and , has lower ascii code than , where

Given a set of Super Strings , a Hyper String is a string that can be constructed by concatenation of some Super Strings of the set . We can use each Super String as many times as we want.

Given set , you have to compute the number of Hyper Strings with length no greater than .

Input Format

The first line of input contains two integers, (the number of Super Strings in ) and . The next lines describe the Super Strings in set .

Constraints

and are not greater than .

Output Format

Output an integer which is the number of possible Hyper Strings that can be derived. Since it may not fit in bit integer, print the output module . (i.e. answer = answer % )

Sample Input

2 3  
a  
ab

Sample Output

7

Explanation

In the example all the Hyper Strings are : “” (empty string), ““, ““, ““, ““, ““, and ““.

Limbajul de programare folosit: cpp20

Cod:

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

static const int AB = 10;
static const int MAX_MASK = 1 << AB;
static const long long MOD = 1000000007LL;

long long hyperStrings(int m, vector<int> arr) {
    sort(arr.begin(), arr.end());

    vector<char> reachable(MAX_MASK, 0);
    reachable[0] = 1;

    for (int mask : arr) {
        int lowBitBound = 1 << __builtin_ctz((unsigned)mask);
        for (int prev = lowBitBound - 1; prev >= 0; --prev) {
            if (reachable[prev]) {
                reachable[prev | mask] = 1;
            }
        }
    }

    vector<int> superMasks;
    superMasks.reserve(MAX_MASK);
    for (int mask = 0; mask < MAX_MASK; ++mask) {
        if (reachable[mask]) superMasks.push_back(mask);
    }

    vector<array<int, AB>> dp(m + 1);
    for (int len = 0; len <= m; ++len) {
        for (int j = 0; j < AB; ++j) dp[len][j] = 0;
    }

    // Empty string: previous ending letter can be treated as 'j'.
    dp[0][AB - 1] = 1;

    long long ans = 0;

    for (int len = 0; len <= m; ++len) {
        for (int last = 0; last < AB; ++last) {
            ans += dp[len][last];
            if (ans >= MOD) ans -= MOD;

            if (dp[len][last] == 0) continue;

            for (int mask : superMasks) {
                int add = __builtin_popcount((unsigned)mask);
                int first = __builtin_ctz((unsigned)mask);
                if (len + add > m) continue;
                if (first > last) continue;

                int ending = 31 - __builtin_clz((unsigned)mask);
                int &ref = dp[len + add][ending];
                ref += dp[len][last];
                if (ref >= MOD) ref -= MOD;
            }
        }
    }

    return ans;
}

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

    int n, m;
    cin >> n >> m;

    vector<int> masks(n, 0);
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (char c : s) {
            masks[i] |= 1 << (c - 'a');
        }
    }

    cout << hyperStrings(m, masks) << '\n';
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464640726

Link challenge: https://www.hackerrank.com/challenges/hyper-strings/problem

Hyper Strings