oj.uz

Submission #477796

# Submission time Handle Problem Language Result Execution time Memory
477796 2021-10-03T19:51:02 Z mychecksedad Trener (COCI20_trener) C++17
55 / 110
 2000 ms 38852 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;


ll fp(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) (res *= a) %= MOD;
        (a*=a)%=MOD;
        b>>=1;
    }
    return res;
}
int n, k;
ll dp[55][1600], h[55][1600][55];
string s[55][1600];
void solve(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) for(int j = 1; j <= k; ++j) cin >> s[i][j];
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= k; ++j){
            h[i][j][0] = 0;
            ll e = 1;
            for(int c = 1; c <= i; ++c, (e*=31)%=MOD){
                h[i][j][c] = (h[i][j][c - 1] + e * (s[i][j][c - 1] - 'a')) % MOD;
            }
        }
    }
    for(int i = 0; i <= n; i++) for(int j = 0; j <= k; ++j) dp[i][j] = 0;
    for(int j = 1; j <= k; ++j) dp[1][j] = 1;
    for(int i = 2; i <= n; ++i){
        for(int j = 1; j <= k; ++j){
            for(int back = 1; back <= k; ++back){
                ll l = h[i][j][i - 1];
                ll r = ((((h[i][j][i] - h[i][j][1]) * fp(31 * 1LL, MOD-2))%MOD)+MOD)%MOD;
                if(l == h[i - 1][back][i - 1] || r == h[i - 1][back][i - 1]){
                    (dp[i][j] += dp[i - 1][back]) %= MOD;
                } 
            }
        }
    }
    ll sum = 0;
    for(int i = 1; i <= k; ++i) (sum += dp[n][i]) %= MOD;
    cout << sum;
}



int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
    }
    return 0;
 
}

Compilation message

trener.cpp: In function 'int main()':
trener.cpp:61:16: warning: unused variable 'aa' [-Wunused-variable]
   61 |     int T = 1, aa;
      |                ^~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3148 KB Output is correct
2 Correct 2 ms 3148 KB Output is correct
3 Correct 2 ms 3148 KB Output is correct
4 Correct 2 ms 3148 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 5956 KB Output is correct
2 Correct 78 ms 5920 KB Output is correct
3 Correct 77 ms 5916 KB Output is correct
4 Correct 77 ms 5912 KB Output is correct
5 Correct 78 ms 5916 KB Output is correct
6 Correct 80 ms 5836 KB Output is correct
7 Correct 77 ms 5836 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3148 KB Output is correct
2 Correct 2 ms 3148 KB Output is correct
3 Correct 2 ms 3148 KB Output is correct
4 Correct 2 ms 3148 KB Output is correct
5 Correct 78 ms 5956 KB Output is correct
6 Correct 78 ms 5920 KB Output is correct
7 Correct 77 ms 5916 KB Output is correct
8 Correct 77 ms 5912 KB Output is correct
9 Correct 78 ms 5916 KB Output is correct
10 Correct 80 ms 5836 KB Output is correct
11 Correct 77 ms 5836 KB Output is correct
12 Execution timed out 2078 ms 38852 KB Time limit exceeded
13 Halted 0 ms 0 KB -