Submission #233980

#	Time	Username	Problem	Language	Result	Execution time	Memory
233980		doowey	Trener (COCI20_trener)	C++14	110 / 110	817 ms	3608 KiB

trener

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 51;
const int K = 1510;
const int MOD = (int)1e9 + 7;
const int mod = 998244353;
const int AL = 26;

int h1[N][K];
int h2[N][K];
int hh[N][K];
int dp[N][K];

int main(){ 
  fastIO;
  int n, k;
  cin >> n >> k;
  string cur;
  int sum, pwr;
  for(int i = 1 ; i <= n; i ++ ){
    for(int j = 0 ; j < k ; j ++ ){
      cin >> cur;
      sum = 0, pwr = 1;
      for(int f = 0; f < i; f ++ ){
        sum = (sum + ((cur[f] - 'a' + 1) * 1ll * pwr) % mod) % mod;
        pwr = (pwr * 1ll * AL) % mod;
      }
      hh[i][j] = sum;
      sum = 0, pwr = 1;
      for(int f = 0; f < i - 1; f ++ ){
        sum = (sum + ((cur[f] - 'a' + 1) * 1ll * pwr) % mod) % mod;
        pwr = (pwr * 1ll * AL) % mod;
      }
      h1[i][j] = sum;
      sum = 0, pwr = 1;
      for(int f = 1; f < i; f ++ ){
        sum = (sum + ((cur[f] - 'a' + 1) * 1ll * pwr) % mod) % mod;
        pwr = (pwr * 1ll * AL) % mod;
      }
      h2[i][j] = sum;
    }
  }
  for(int i = 0 ; i < k ; i ++ ) dp[n][i] = 1;
  for(int i = n - 1; i >= 1; i -- ){
    for(int j = 0 ; j < k ; j ++ ){
      for(int x = 0; x < k ; x ++ ){
        if(hh[i][j] == h1[i + 1][x] || hh[i][j] == h2[i + 1][x]){
          dp[i][j]=(dp[i][j]+dp[i+1][x])%MOD;
        }
      }
    }
  }
  int ans = 0;
  for(int i = 0 ; i < k ; i ++ ) ans = (ans + dp[1][i]) % MOD;
  cout << ans << "\n";
  return 0;
}

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