Codeforces Round #425 (Div. 2), problem: (E) Vasya and Shifts Solution In C/C++

#include<bits/stdc++.h>
#define oo 0x3f3f3f3f
#define cl(x) memset(x, 0, sizeof(x))
#define mp make_pair
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define mo 1000000007
#define maxn 510
typedef long long ll;
using namespace std;
void gn(int &x) {
x = 0; char ch = getchar();
while (ch < ‘0’ || ch > ‘9’) ch = getchar();
while (ch >= ‘0’ && ch <= ‘9’)
x = x * 10 + ch – ‘0’, ch = getchar();
}
int n, m, q, end, a[maxn][maxn], x[maxn], b[maxn];
int ans;
char s[maxn], t[maxn];
void gauss() {
int p = 1;
for (int i = 1; i <= n && p <= m; ++i, ++p) {
for (int j = i; j <= n; ++j)
if (a[j][p] != 0) {
for (int k = 1; k <= m; ++k) swap(a[j][k], a[i][k]);
break;
}
if (!a[i][p]) {
–i; continue;
}
for (int j = i + 1; j <= n; ++j)
if (a[j][p] != 0) {
int t = a[j][p];
for (int k = p; k <= m; ++k) {
a[j][k] = a[j][k] * a[i][p] – a[i][k] * t;
a[j][k] = (a[j][k] % 5 + 5) % 5;
}
}
}
for (int i = 1; i <= n; ++i) {
bool flag = 1;
for (int j = 1; j <= m; ++j)
if (a[i][j]) flag = 0, end = i;
if (flag) ans = 5ll * ans % mo;
}
}
bool check() {
for (int i = 1; i <= end; ++i) {
int p = 1; while (a[i][p] == 0) ++p;
if (b[p] != 0) {
int t = b[p];
for (int k = p; k <= m; ++k) {
b[k] = b[k] * a[i][p] – a[i][k] * t;
b[k] = (b[k] % 5 + 5) % 5;
}
}
}
bool flag = 1;
for (int i = 1; i <= m; ++i)
if (b[i]) flag = 0;
return flag;
}
int main() {
gn(n); gn(m);
for (int i = 1; i <= n; ++i) {
scanf(“%s”, s + 1);
for (int j = 1; j <= m; ++j)
a[i][j] = s[j] – ‘a’;
}
ans = 1;
gauss();
gn(q);
while (q–) {
scanf(“%s”, t + 1);
for (int i = 1; i <= m; ++i) b[i] = t[i] – ‘a’;
if (check()) printf(“%d\n”, ans); else puts(“0”);
}
return 0;
}

Advertisement

spot_img

Why Viral Kitchen Gadgets...

📢 As an Amazon Associate, I earn from qualifying...

US and rivals spar...

According to a report by Al Jazeera, diplomatic tensions...

Why Viral Kitchen Gadgets...

📢 As an Amazon Associate, I earn from qualifying...

Curt Cignetti has built...

College football is often dictated by resources, prestige, and...

I Tried Viral Kitchen...

📢 As an Amazon Associate, I earn from qualifying...

Top House Budget Dem...

In response to growing scrutiny over the reliability and...

Why Viral Kitchen Gadgets Is Currently Breaking the Internet

📢 As an Amazon Associate, I earn from qualifying purchases.Most products in this category disappoint within weeks. Cheap materials, vague instructions, and results that...

US and rivals spar over next UN boss as race lurches towards deadline

According to a report by Al Jazeera, diplomatic tensions among global powers have intensified as the United Nations nears the deadline to select its...

Why Viral Kitchen Gadgets Is Currently Breaking the Internet

📢 As an Amazon Associate, I earn from qualifying purchases.If you had told me six months ago that a single purchase would change how...

Curt Cignetti has built what Lincoln Riley can’t at USC: a team that knows how to win

College football is often dictated by resources, prestige, and five-star recruiting classes. Yet, the stark contrast between Curt Cignetti’s Indiana Hoosiers and Lincoln Riley’s...

I Tried Viral Kitchen Gadgets For 30 Days Here Is the Honest Truth

📢 As an Amazon Associate, I earn from qualifying purchases.There comes a point when you realise that tolerating a frustrating situation is costing you...

Top House Budget Dem Boyle: I’d Support ‘Major Appropriation’ for FAA Overhaul

In response to growing scrutiny over the reliability and resilience of national aviation infrastructure, Representative Brendan Boyle (D-PA) has publicly signaled strong support for...

I Tried Viral Kitchen Gadgets For 30 Days Here Is the Honest Truth

📢 As an Amazon Associate, I earn from qualifying purchases.After putting the Viral Kitchen Gadgets through a proper 30-day real-world test, I can tell...

‘Feeling good’ – Shams Charania provides Luka Doncic, Austin Reaves injury updates

Basketball fans can breathe a collective sigh of relief following the latest Luka Doncic Austin Reaves injury updates delivered by trusted NBA insider Shams...

The Ultimate Viral Kitchen Gadgets Guide You Didnt Know You Needed

📢 As an Amazon Associate, I earn from qualifying purchases.Most products in this category disappoint within weeks. Cheap materials, vague instructions, and results that...