Tìm số cặp chuỗi kỳ diệu độ dài L trong C++

Giả sử chúng ta có hai chuỗi str1 và str2, chúng ta phải tìm số cặp kỳ diệu độ dài L. Hai chuỗi sẽ là kỳ diệu nếu với mọi chỉ số i, str1[i] < str2[i]. Chúng ta phải đếm số cặp vì số rất lớn, nên trả về kết quả modulo 10⁹. Các chuỗi chỉ chứa chữ cái thường.

Cách tiếp cận rất đơn giản. Như ta thấy, nếu độ dài L = 1, và chỉ số i = 1 chứa 'a' trong str1 thì chỉ số i = 1 của str2 sẽ chứa từ 'b' đến 'z' nên 25 tổ hợp, cho ký tự tiếp theo sẽ là 24 tổ hợp, nên sẽ là 25 + 24 + ... + 1 = 325. Bây giờ với L = 2, sẽ là 325². Với độ dài L, sẽ là 325^L. Nếu rất lớn, thì tìm modulo 10⁹.

Ví dụ

#include<iostream> #include<cmath> using namespace std; int power(int a, unsigned int b, int mod) {    int res = 1;    a = a % mod;    while (b > 0) {       if (b & 1)          res = (res * a) % mod;       b = b >> 1;       a = (a * a) % mod;    }    return res; } int main() {    int L = 2, P = pow(10, 9);    int res = power(325, L, P);    cout << "Combinations: " << res << endl; }

Kết quả

Combinations: 105625