Kiến thức cần biết: Đồng dư, chia để trị
Với subtask 1 (80%), ta có thể dùng vòng lặp $n$ lần để tính đồng dư của $a^n$.
Với subtask 2 (20%), sử dụng thuật toán chia để trị để tính nhanh $a^n$ trong độ phức tạp $O(log(n))$.
Chỉ cần kiểm tra một xâu $s$ có đối xứng hay không. Cách đơn giản để lập trình là tạo ra một $t$ giống xâu $s$. Sau đó đảo ngược xâu $t$ rồi so sánh với $s$. Sử dụng hàm reverse(begin(t), end(t) để đảo ngược.
Sử dụng phương pháp đếm phân phối là giải quyết được hết các subtask. Chú ý, khởi tạo mảng đếm phân phối ngoài hàm int main() , không thể lưu trữ mảng có $10^7$ phần tử trong hàm int main().
Subtask 1, có thể sử dụng duyệt phân tập.
Đây là một bài toán QHĐ (Quy hoạch động). Gọi F[i][j] là tổng giá trị lớn nhất từ các cách mua từ gói hàng $1…i$ và có có tổng khối lượng không quá $j$. Ta có kết quả của bài toán là $F[n][m]$, công thức truy hồi:
$$ F[i][j] \leftarrow F[i-1][j-w[i]]+v[i] $$