Connection Status:
Competition Arena > PairsOfStrings

PairsOfStrings

SRM 603 · 2013-12-22 · by lyrically

SRM 603 · 2013-12-22 · by lyrically · Dynamic Programming, Math
Class Name: PairsOfStrings
Return Type: int
Method Name: getNumber
Arg Types: (int, int)
Problem Statement

Problem Statement

We are interested in pairs of strings (A, B) that satisfy the following conditions:
  • A and B consist of exactly n characters each.
  • Each character in A and B is one of the first k lowercase letters of the English alphabet.
  • There exists a string C such that A + C = C + B. Here, + denotes string concatenation.
For example, if n = 3 and k = 4 then one valid pair of strings is ("aad", "daa"): both strings have length 3, only the first 4 letters are used in each of them, and C = "aa" shows that the third condition is satisfied as well.

You are given the ints n and k. Find the number of such pairs of strings, and return the number modulo 1,000,000,007.

Constraints

  • n will be between 1 and 1,000,000,000, inclusive.
  • k will be between 1 and 26, inclusive.
Examples
0)
2
2
Returns: 6

The following 6 pairs satisfy the conditions: ("aa", "aa"), ("ab", "ab"), ("ab", "ba"), ("ba", "ab"), ("ba", "ba"), ("bb", "bb").

1)
3
2
Returns: 20
2)
3
4
Returns: 184
3)
6
2
Returns: 348
4)
100
26
Returns: 46519912

Submissions are judged against all 95 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PairsOfStrings with a public method int getNumber(int n, int k) · 95 test cases · 2 s / 256 MB per case

Submitting as anonymous