สมมติว่าเรามีสตริงสองสาย 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