Thành phố Cuồng loạn

Chuỗi ký tự nâng cao Băm chuỗi Băm đa thức \(f(s)=\sum^l_{r=1}s_i\times b^{i-1}\pmod M\)。 Băm ma trận Phù hợp cho việc băm tập hợp chuỗi. Nếu dùng băm đa thức, tập hợp chuỗi \(\{ab,bd\}\) và \(\{ad,bd\}\) sẽ có cùng giá trị băm. Ta biểu diễn mỗi ký tự thành một ma trận \(2\times 2\). Với chuỗi giống nhau thì nhân ma trận, khác nhau thì cộng ma ...

T1 link Đây là một bài toán khá đơn giản, có thể giải ngay bằng phương pháp quét đường, nhưng đáng tiếc là cách tiếp cận đó gây ra TLE, chỉ đạt được 80 điểm. Giải pháp thực sự lại đơn giản đến bất ngờ. Có thể giải bài này bằng cách duyệt từ cuối về đầu một vòng lặp 1e7, mỗi lần cộng thêm giá trị lớn nhất. code #include <bits/stdc++.h> usi ...