Submission #219371

#TimeUsernameProblemLanguageResultExecution timeMemory
219371kartelTrener (COCI20_trener)C++14
110 / 110
1148 ms114760 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> #define in(x) freopen(x, "r", stdin) #define out(x) freopen(x, "w", stdout) #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-O3") #define F first #define S second #define pb push_back #define N +400500 #define M ll(1e9 + 7) #define sz(x) (int)x.size() #define re return #define oo ll(1e18) #define el '\n' using namespace std; //using namespace __gnu_pbds; //typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef long long ll; typedef long double ld; bool go[51][1501][1501]; ll f[51][1501], ans, hsh[51][1501], p[51]; int i, j, k, m, p1, n; string s[51][1501]; ll sm(ll x, ll y) {return (x + y) % M;} int main() { srand(time(0)); ios_base::sync_with_stdio(0); iostream::sync_with_stdio(0); ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); // in("input.txt"); // out("output.txt"); cin >> n >> m; p[0] = 1; for (i = 1; i <= n; i++) p[i] = (p[i - 1] * 31) % M; for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) { cin >> s[i][j]; hsh[i][j] = 0; for (k = 0; k < i; k++) hsh[i][j] = sm(hsh[i][j], (s[i][j][k] - 'a' + 1) * p[k] % M); } for (i = 1; i < n; i++) { for (j = 1; j <= m; j++) { for (k = 1; k <= m; k++) { if (hsh[i][j] * 31 % M == (hsh[i + 1][k] - (s[i + 1][k][0] - 'a' + 1) + M) % M) go[i][j][k] = 1; if (hsh[i][j] == (M + hsh[i + 1][k] - (s[i + 1][k][i] - 'a' + 1) * p[i] % M) % M) go[i][j][k] = 1; } } } for (i = 1; i <= m; i++) f[1][i] = 1; for (i = 1; i < n; i++) for (j = 1; j <= m; j++) for (k = 1; k <= m; k++) if (go[i][j][k]) f[i + 1][k] = sm(f[i][j], f[i + 1][k]); ans = 0; for (i = 1; i <= m; i++) ans = sm(f[n][i], ans); cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...