मान लीजिए हमारे पास 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] मान्य नहीं हैं इसलिए 6 स्ट्रिंग्स हैं।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- p := 10^9+7
- यदि n, 1 के समान है, तो
- m mod p लौटाएं
- यदि 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
