Submission #223220

#	Time	Username	Problem	Language	Result	Execution time	Memory
223220		lyc	Trener (COCI20_trener)	C++14	110 / 110	528 ms	6644 KiB

trener

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

#define SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int MX_N = 55;
const int MX_K = 1505;

const int MOD = 1e9+7;

const int P = 101, Q = 1e9+7;

int N, K;
string S[MX_N][MX_K];
pair<int,int> h[MX_N][MX_K];

int dp[MX_N][MX_K];

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

    cin >> N >> K;
    FOR(i,1,N){
        FOR(j,1,K) cin >> S[i][j];
    }

    FOR(j,1,K) {
        int cur = 0;
        FOR(k,0,N-2) {
            cur = ((1LL*cur*P) % Q + S[N][j][k]-'a') % Q;
        }
        h[N][j].first = cur;
        cur = 0;
        FOR(k,1,N-1) {
            cur = ((1LL*cur*P) % Q + S[N][j][k]-'a') % Q;
        }
        h[N][j].second = cur;
        dp[N][j] = 1;
    }

    RFOR(i,N-1,1){
        FOR(j,1,K){
            dp[i][j] = 0;

            int cur = 0;
            FOR(k,0,i-2) {
                cur = ((1LL*cur*P) % Q + S[i][j][k]-'a') % Q;
            }
            h[i][j].first = cur;
            cur = ((1LL*cur*P) % Q + S[i][j][i-1]-'a') % Q;
            //cout << "i j " << i << " " << j << " :: " << cur << endl;

            FOR(k,1,K) {
                if (cur == h[i+1][k].first || cur == h[i+1][k].second) {
                    //cout << i << " " << j << " :: " << i+1 << " " << k << endl;
                    dp[i][j] += dp[i+1][k];
                    if (dp[i][j] >= MOD) dp[i][j] -= MOD;
                }
            }

            cur = 0;
            FOR(k,1,i-1) {
                cur = ((1LL*cur*P) % Q + S[i][j][k]-'a') % Q;
            }
            h[i][j].second = cur;
        }
    }

    int ans = 0;
    FOR(i,1,K){
        ans += dp[1][i];
        if (ans >= MOD) ans -= MOD;
    }
    cout << ans << '\n';
}

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