สมมติว่าเรามีสตริงสองสาย str1 และ str2 เราต้องหาคู่เวทย์มนตร์ที่มีความยาว L จำนวนหนึ่ง สองสตริงจะเป็นเวทย์มนตร์หากสำหรับทุกดัชนี I str1[i]
วิธีการนั้นง่าย ดังที่เราเห็น หากความยาวคือ L =1 และดัชนี i =1 กำลังถือ 'a' ใน str1 ดัชนี i =1 ของ str2 จะเก็บจาก 'b' ถึง 'z' ดังนั้น 25 ชุดสำหรับอักขระตัวต่อไป มันจะเป็น 24 ชุด ดังนั้นมันจะเป็น 25 + 24 + . . . +1 =325 ตอนนี้สำหรับ L =2 จะเป็น 3252 สำหรับความยาว L จะเป็น 325L หากมีขนาดใหญ่มาก ให้หาโมดูลัส 109ตัวอย่าง
#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;
} ผลลัพธ์
Combinations: 105625
