普及⏱ 1000ms💾 256MB#P5127🏷️ 动态规划递推

题目描述

实验室培养一种特殊菌落:每份成熟菌落每过 $x$ 天分裂出 $y$ 份新菌落,新菌落要经过 2 天培养才能成熟;成熟菌落永不死亡。第 1 天只有 1 份成熟菌落,且新成熟的菌落要再等 $x$ 天后才开始分裂。

求 $z$ 天后培养皿中成熟菌落的份数。

输入格式

一行,三个整数 $x, y, z$,用空格分隔。

输出格式

一行,一个整数:$z$ 天后成熟菌落的份数。

数据范围

$$0 \le x \le 20,\quad 1 \le y \le 20,\quad x \le z \le 50$$

样例输入 #1
1 2 8
样例输出 #1
37
样例输入 #2
1 1 1
样例输出 #2
1