Submission #845292

#	Time	Username	Problem	Language	Result	Execution time	Memory
845292		vjudge1	Trener (COCI20_trener)	C++17	110 / 110	234 ms	4872 KiB

trener

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

#define ll long long
const int N = 2e5 + 5, MOD = 1e9 + 7, p = 29, p1 = 37;

ll dp[55][1505], h[2][55][1505][3], us[60], us2[60];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    us[0] = 1;
    us2[0] = 1;

    for(int i = 1; i < 60; i++)
    {
        us[i] = (us[i - 1] * p) % MOD;
        us2[i] = (us2[i - 1] * p1) % MOD;
    }

    int n, k;
    cin >> n >> k;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            string str;
            cin >> str;

            str = "#" + str;

            for(int l = 1; l <= i; l++)
            {
                h[0][i][j][0] = (h[0][i][j][0] + (str[l] - 'a' + 1) * us[l]) % MOD;              
                h[1][i][j][0] = (h[1][i][j][0] + (str[l] - 'a' + 1) * us2[l]) % MOD;
                if(l == i - 1)
                {
                    h[0][i][j][1] = h[0][i][j][0];
                    h[1][i][j][1] = h[1][i][j][0];
                }
            }

            for(int l = 2; l <= i; l++)
            {
                h[0][i][j][2] = (h[0][i][j][2] + (str[l] - 'a' + 1) * us[l - 1]) % MOD;
                h[1][i][j][2] = (h[1][i][j][2] + (str[l] - 'a' + 1) * us2[l - 1]) % MOD;
            }

     //       cout << i << " " << j << " " << h[i][j][0] << " " << h[i][j][1] << " " << h[i][j][2] << '\n';
        }
    }

    for(int i = 1; i <= k; i++)
        dp[1][i] = 1;

    for(int i = 1; i < n; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            for(int l = 1; l <= k; l++)
            {
                if(h[0][i][j][0] == h[0][i + 1][l][1] and h[1][i][j][0] == h[1][i + 1][l][1])
                {
                    if(dp[i + 1][l] == 0)
                    {
                        dp[i + 1][l] = dp[i][j];
                    }
                    else
                    {
                        dp[i + 1][l] = (dp[i + 1][l] + dp[i][j]) % MOD;
                    }
                }
                else if(h[0][i][j][0] == h[0][i + 1][l][2] and h[1][i][j][0] == h[1][i + 1][l][2])
                {
                    if(dp[i + 1][l] == 0)
                    {
                        dp[i + 1][l] = dp[i][j];
                    }
                    else
                    {
                        dp[i + 1][l] = (dp[i + 1][l] + dp[i][j]) % MOD;
                    }
                }
            }
        }
    }

    // for(int i = 1; i <= n; i++)
    // {
    //     for(int j = 1; j <= k; j++)
    //     {
    //         cout << dp[i][j] << " " ;
    //     }
    //     cout << '\n';
    // }

    ll ans = 0;

    for(int i = 1; i <= k; i++)
        ans = (ans + dp[n][i]) % MOD;

    cout << ans << '\n';
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55