在C ++中找到长度为L的神奇字符串对的数量。
假设我们有两个字符串str1和str2,我们必须找到许多长度为L的神奇对。如果对于每个索引I,str1[i]<str2[i],那么两个字符串将是神奇的。由于数目非常大,我们必须计算成对的数目,然后使用模109返回答案。字符串将仅包含小写字母。
该方法很简单。如我们所见,如果长度为L=1,并且索引i=1持有'a',则在str1中,str2的索引i=1将保持从'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