ধরুন আমাদের m অক্ষর সংখ্যা এবং আরেকটি মান n আছে। আমাদের এই m অক্ষরগুলি থেকে নিয়ে অক্ষর দিয়ে তৈরি n দৈর্ঘ্যের স্ট্রিংগুলির সংখ্যা গণনা করতে হবে এবং স্ট্রিংটির দৈর্ঘ্যের 1-এর বেশি কোনও প্যালিনড্রোমিক সাবস্ট্রিং নেই৷ যদি উত্তরটি খুব বড় হয় তবে ফলাফলটি 10^9+7 দ্বারা পরিবর্তন করুন৷
সুতরাং, যদি ইনপুটটি n =2 m =3 এর মত হয়, তাহলে আউটপুট 6 হবে কারণ m =3, তাই যদি বর্ণমালাগুলি {x,y,z} হয়, আমরা স্ট্রিং তৈরি করতে পারি যেমন:[xx, xy,xz ,yx,yy,yz,zx,zy,zz] কিন্তু [xx,yy,zz] বৈধ নয় তাই ৬টি স্ট্রিং আছে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- p :=10^9+7
- যদি n 1 এর মত হয়, তাহলে
- মি মোড পি রিটার্ন করুন
- যদি n 2 এর মত হয়, তাহলে
- রিটার্ন m *(m - 1) mod p
- যদি m <=2, তারপর
- রিটার্ন 0
- রিটার্ন m*(m-1) * ((m-2)^(n-2) mod p) mod p
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
def solve(n, m):
p = 10**9+7
if n == 1:
return m % p
if n == 2:
return m * (m - 1) % p
if m <= 2:
return 0
return m * (m - 1) * pow(m - 2, n - 2, p) % p
n = 2
m = 3
print(solve(n, m)) ইনপুট
3, [1,2,3,4,1]
আউটপুট
6
