Submission #845267

#	Time	Username	Problem	Language	Result	Execution time	Memory
845267		vjudge1	Trener (COCI20_trener)	C++17	55 / 110	126 ms	2640 KiB

trener

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

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

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

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

    us[0] = 1;

    for(int i = 1; i < 60; i++)
    {
        us[i] = (us[i - 1] * p) % 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[i][j][0] = (h[i][j][0] + (str[l] - 'a' + 1) * us[l]) % MOD;
                if(l == i - 1)
                    h[i][j][1] = h[i][j][0];
            }

            for(int l = 2; l <= i; l++)
            {
                h[i][j][2] = (h[i][j][2] + (str[l] - 'a' + 1) * us[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[i][j][0] == h[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[i][j][0] == h[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: 0 / 55