หาจำนวนคู่เวทมนต์ (Magical Pairs) ของสตริงความยาว L ใน C++

สมมติว่าเรามีสตริงสองตัว str1 และ str2 เราต้องหาจำนวนคู่เวทมนต์ (Magical Pairs) ของความยาว L สองสตริงจะเป็นคู่เวทมนต์หากสำหรับดัชนีทุก i str1[i] < str2[i] เราต้องนับจำนวนคู่ เนื่องจากจำนวนมากมาย ให้คืนคำตอบโดยใช้ modulo 10^9 สตริงจะมีเฉพาะตัวอักษรพิมพ์เล็ก

วิธีการง่ายๆ คือ ถ้าความยาว L = 1 และดัชนี i = 1 มี 'a' ใน str1 ดัชนี i = 1 ของ str2 จะมี 'b' ถึง 'z' รวม 25 แบบ สำหรับตัวอักษรถัดไป 24 แบบ รวมเป็น 25 + 24 + ... + 1 = 325 ตอนนี้ L = 2 จะเป็น 325^2 สำหรับความยาว L จะเป็น 325^L ถ้ามากมาย หา modulus 10^9

ตัวอย่างโค้ด

#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