青蛙过河_牛客博客

设 $A(n, m)$ 是能过河的青蛙的数量， $n$ 为石墩的数量， $m$ 为荷叶的数量。
则 $A(0, m) = m+1$ 。这是比较显然的，让青蛙在每个荷叶上一只，再让一只跳到对面，荷叶上的青蛙然后跳到对面。
对于 $A(n, m)$ , 我们先河对岸的落脚点，将一个河墩视为对岸，则，最多能跳 $A(n-1, m)$ 个青蛙过去。此时还剩下 $n-2$ 个河墩，如法炮制，会有 $A(n,m) = \Sigma_{i=0}^{n-1}A(i, m) + A(0, m)$
为什么会多一个 $A(0, m)$ 呢，因为当所有石墩都占满了青蛙后，我们就可以选择跳对岸了。

解得 $A(n, m) = (m+1)2^{n}$

这题我没想出来，感谢楼上大佬的思路

int main(){
    int n, m; cin >> n >> m;
    cout << (m+1)*(1<<n) << endl;

    return 0;
}