Given a length n, count the number of strings of length n that can be made using ‘a’, ‘b’ and ‘c’ with at-most one ‘b’ and two ‘c’s allowed.
Example 1:
Input: n = 1
Output: 3
Explanation: Possible strings are: "a",
"b" and "c"
Example 2:
Input: n = 3
Output: 19
Explanation: Number of strings with 3 
occurrances of a: 1
2-a and 1-b: 3
2-a and 1-c: 3
1-a, 1-b and 1-c: 6
1-a and 2-c: 3
1-b and 2-c: 3
So, total number of strings of length 3
is 1 + 3 + 3 + 6 + 3 + 3 = 19
Your Task:  
You don't need to read input or print anything. Your task is to complete the function countStr() which takes the n as inputs and returns the answer.
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ n ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3

class Solution:

    def countStr(self, n):
        # code here

Solutions:
class Solution:

	def countStr(self, n):
		return int(1 + 2 * n + n * (n - 1) * (n + 1) / 2)


class Solution:

	def countStr(self, n):
		r1 = 2 * n
		r2 = n * (n - 1) // 2
		r3 = n * (n - 1)
		r4 = n * (n - 1) * (n - 2) // 2
		return 1 + r1 + r2 + r3 + r4


class Solution:

	def countStr(self, n):
		return 1 + n * 2 + n * (n * n - 1) // 2

	def count(self, i, b, c):
		if i == self.n:
			return 1
		(count1, count2, count3) = (0, 0, 0)
		count1 = self.count(i + 1, b, c)
		if b > 0:
			count2 = self.count(i + 1, b - 1, c)
		if c > 0:
			count3 = self.count(i + 1, b, c - 1)
		return count1 + count2 + count3


class Solution:

	def factorial(self, N):
		p = 1
		for i in range(1, N + 1):
			p = p * i
		return p

	def countStr(self, n):
		c = 1
		c += n
		c += n
		c += n * (n - 1)
		c += n * (n - 1) * (n - 2) // 2
		c += n * (n - 1) // 2
		return c


class Solution:

	def countStr(self, n):
		return int((n * n * n + 3 * n + 2) / 2)


class Solution:

	def countStr(self, n):
		if n == 1:
			return 3
		ans = 1
		ans += n
		ans += n
		ans += n * (n - 1)
		ans += n * (n - 1) // 2
		ans += n * (n - 1) * (n - 2) // 2
		return ans


class Solution:

	def countStr(self, n):
		count = 0
		if n >= 1:
			count += 1
			count += n
			count += n
			if n >= 2:
				count += n * (n - 1)
				count += n * (n - 1) // 2
				if n >= 3:
					count += n * (n - 1) * (n - 2) // 2
		return count


class Solution:

	def countStr(self, n):
		res = 1
		res += 2 * n
		res += n * (n - 1)
		res += n * (n - 1) * (n - 2) // 2
		res += n * (n - 1) // 2
		return res


class Solution:

	def countStr(self, n):
		only_a = 1
		a_b = n
		a_c = n
		a_cc = n * (n - 1) / 2
		a_b_c = n * (n - 1)
		a_b_cc = n * (n - 1) * (n - 2) / 2
		return int(only_a + a_b + a_c + a_cc + a_b_c + a_b_cc)


class Solution:

	def countStr(self, n):
		if n == 1:
			return 3
		if n == 2:
			return 8
		else:
			only_a = 1
			a_b = n
			a_c = n
			a_cc = n * (n - 1) / 2
			a_b_c = n * (n - 1)
			a_b_cc = n * (n - 1) * (n - 2) / 2
		return int(only_a + a_b + a_c + a_cc + a_b_c + a_b_cc)


class Solution:

	def countStr(self, n):
		ret_val = 2 * n + 1 + n * (n - 1) + n * (n - 1) * (n - 2) // 2 + n * (n - 1) // 2
		return ret_val


class Solution:

	def countStr(self, l):
		return 1 + n * 2 + n * (n * n - 1) // 2


class Solution:

	def solve(self, i, n, b=0, c=0):
		if i == n:
			return 1
		ans = 0
		if b < 1:
			ans += self.solve(i + 1, n, b + 1, c)
		if c < 2:
			ans += self.solve(i + 1, n, b, c + 1)
		ans += self.solve(i + 1, n, b, c)
		return ans

	def countStr(self, n):
		return (n * n * n + 3 * n + 2) // 2
		return self.solve(0, n)


class Solution:

	def countStr(self, n):
		return 1 + 2 * n + 3 * n * (n - 1) // 2 + n * (n - 1) * (n - 2) // 2


class Solution:

	def countStr(self, n):
		val1 = n * n - 1
		val2 = n * 2
		res = 1 + val2 + val1 * n // 2
		return res


class Solution:

	def countStr(self, n):
		res = 0
		res += 1 + n * 2 + n * (n * n - 1) / 2
		return int(res)


class Solution:

	def countStr(self, n):
		if n <= 2:
			return 3 * n
		b = n + n * (n - 1) + n * (n - 1) * (n - 2) // 2
		c = n + n * (n - 1) // 2
		return 1 + b + c


import math

class Solution:

	def countStr(self, n):
		return 1 + n * 2 + n * (n * n - 1) // 2


class Solution:

	def countStr(self, n):
		tot = n + n + 1 + n * (n - 1) + n * (n - 1) // 2 + n * (n - 1) * (n - 2) // 2
		return tot


class Solution:

	def countStr(self, n):
		if n == 1:
			return 3
		elif n == 2:
			return 8
		else:
			ans = 2 * n + 3 * (n * (n - 1)) // 2 + n * (n - 1) * (n - 2) // 2 + 1
			return ans


class Solution:

	def countStr(self, n):
		return int((n * n * n + 3 * n + 2) / 2)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		solObj = Solution()
		print(solObj.countStr(n))


class Solution:

	def countStr(self, n):
		if n == 1:
			return 3
		elif n == 2:
			return 8
		else:
			ans = 1
			ans = ans + n
			ans = ans + n
			ans = ans + n * (n - 1)
			ans = ans + n * (n - 1) / 2
			ans = ans + n * (n - 1) * (n - 2) / 2
			return int(ans)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		solObj = Solution()
		print(solObj.countStr(n))


class Solution:

	def countStr(self, n):
		if n == 0:
			return 0
		ans = 0
		factorial = [1]
		for c in range(3):
			for b in range(2):
				if b + c > n:
					break
				ways = 1
				if b + c < len(factorial):
					ways = ways * factorial[b + c]
				else:
					ways = ways * factorial[-1] * (n + 1 - b - c)
					factorial.append(ways)
				if c == 2:
					ways = ways // 2
				ans += ways
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		solObj = Solution()
		print(solObj.countStr(n))


class Solution:

	def calc(self, cap, a, b, c):
		if cap == 0:
			return 1
		(inc_a, inc_b, inc_c) = (0, 0, 0)
		if a != 0:
			inc_a = self.calc(cap - 1, a - 1, b, c)
		if b != 0:
			inc_b = self.calc(cap - 1, a - 1, b - 1, c)
		if c != 0:
			inc_c = self.calc(cap - 1, a - 1, b, c - 1)
		return inc_a + inc_b + inc_c

	def countStr(self, n):
		return (n ** 3 + 3 * n + 2) // 2
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		solObj = Solution()
		print(solObj.countStr(n))


class Solution:

	def countStr(self, n):
		a = 1 + n + n * (n - 1) // 2
		b = n + n * (n - 1) + n * (n - 1) * (n - 2) // 2
		return a + b


class Solution:

	def countStr(self, n):
		if n == 0:
			return 0
		if n == 1:
			return 3
		if n == 2:
			return 8
		else:
			return int((pow(n, 3) + 3 * n + 2) / 2)


class Solution:

	def countStr(self, n):
		if n == 1:
			return 3
		res = 1
		res += n
		res += n
		res += n * (n - 1)
		res += n * (n - 1) // 2
		res += n * (n - 1) * (n - 2) // 2
		return res


class Solution:

	def countStr(self, n):
		ans = 0
		ans += 1
		ans += n
		ans += n
		ans += n * (n - 1)
		ans += n * (n - 1) // 2
		ans += n * (n - 1) * (n - 2) // 2
		return ans


class Solution:

	def countStr(self, n):
		if n == 1:
			x = 3
		elif n == 2:
			x = 8
		elif n == 3:
			x = 19
		else:
			x = (pow(n, 3) + 3 * n + 2) // 2
		return x


class Solution:

	def countStr(self, n):
		if n <= 1:
			return 3
		elif n == 2:
			return 8
		return int((n ** 3 + n * 3 + 2) / 2)


memory = [0] * 100000

class Solution:

	def countStr(self, n):
		return int(1 + 2 * n + +n * (n - 1) + n * (n - 1) * (n - 2) / 2 + n * (n - 1) / 2)


import math

class Solution:

	def countStr(self, n):
		if n == 1:
			return 3
		answer = 1.0
		answer += n
		answer += n * (n - 1) // 2
		answer += n
		if n >= 3:
			answer += n * (n - 1) * (n - 2) / 2
		answer += n * (n - 1)
		return int(answer)


class Solution:

	def countStr(self, n):
		if n >= 2:
			return int(1 + 2 * n + 1.5 * n * (n - 1) + 0.5 * n * (n - 1) * (n - 2))
		if n == 1:
			return 3


import math

class Solution:

	def cRn(self, n, r):
		return math.factorial(n) // math.factorial(r) // math.factorial(n - r)

	def n_choose_2(self, n):
		return n * (n - 1) // 2

	def countStr(self, n):
		num_str = 0
		if n <= 0:
			return num_str
		if n == 1:
			return n * 3
		num_str += 1
		num_str += n
		n_choose_2 = self.n_choose_2(n)
		if n >= 2:
			num_str += n_choose_2
		if n >= 2:
			num_str += n * (n - 1)
		if n >= 3:
			num_str += n_choose_2 * (n - 2)
		num_str += n
		return num_str


class Solution:

	def countStr(self, n):
		if n == 1:
			return 3
		if n == 2:
			return 8
		if n == 3:
			return 19
		if n > 3:
			return 2 * n + n * (n - 1) // 2 + n * (n - 1) + n * (n - 1) * (n - 2) // 2 + 1


class Solution:

	def countStr(self, n):
		allAs = 1
		oneB = n
		oneC = n
		oneBoneC = n * (n - 1)
		twoCs = oneBoneC // 2
		oneBtwoCs = n * (n - 1) * (n - 2) // 2
		return allAs + oneB + oneC + twoCs + oneBoneC + oneBtwoCs


class Solution:

	def countStr(self, n):
		x = 1 + 2 * n
		y = n * (n * n - 1) // 2
		return x + y


def c(n, r):
	numerator = 1
	counter = n
	while counter > n - r:
		numerator *= counter
		counter -= 1
	den = 1
	counter = r
	while counter >= 1:
		den *= counter
		counter -= 1
	return numerator // den

class Solution:

	def countStr(self, n):
		ans = 1 + n + n
		if n > 1:
			ans = ans + n * (n - 1)
			ans = ans + c(n, 2)
		if n > 2:
			ans = ans + n * c(n - 1, 2)
		return ans


class Solution:

	def countStr(self, n):
		a = 1
		b = n
		c = n
		bc = n * (n - 1)
		bb = n * (n - 1) // 2
		bbc = n * (bb - (n - 1))
		return a + b + c + bc + bb + bbc