Giả sử chúng ta có hai chuỗi str1 và str2, chúng ta phải tìm một số cặp huyền diệu có độ dài L. Hai chuỗi sẽ là ma thuật nếu với mọi chỉ số I, str1 [i]
Cách tiếp cận rất đơn giản. Như chúng ta có thể thấy, nếu độ dài là L =1 và chỉ mục i =1 đang giữ 'a', trong str1 thì chỉ mục i =1 của str2 sẽ giữ từ 'b' đến 'z' vì vậy kết hợp 25, cho ký tự tiếp theo nó sẽ là 24 kết hợp, vì vậy nó sẽ là 25 + 24 +. . . + 1 =325. Bây giờ với L =2, nó sẽ là 3252. Với chiều dài L, nó sẽ là 325L. Nếu nó rất lớn, thì hãy tìm modulus 109. 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;
} Đầu ra
Combinations: 105625
