第十三届蓝桥杯省赛 第9题 (这个dp当时没想出来，就惦记那个暴力，我的建议是remake)

题目 题意: 初始有2升酒，有n次翻倍的机会、m次-1的机会，需要将所有的机会用完。(当还剩0升酒时-1是非法行为)求有多少种方案可以使得最后一次是-1，并且-1以后剩余0升酒。 思路: 当时我都往dp的方向想，现在想来，属于是犯病了。就惦记那个暴力骗分，埋了叭。 f[i][j][k]: 已经用了i个翻倍、j个-1，此时是k升酒的方案数。尽管第三维度可以一直翻倍，但是超过m的值都是没有意义的，因为不可能减少到0了，所以第三维枚举到m就够用。 f[i][j][k] += f[i-1][j][k/2] (i && !(k&1)) f[i][j][k] += f[i][j-1][k+1] (j) 时间复杂度: O(nnn) 代码:

#include
using namespace std;
typedef long long ll;
typedef pair PII;
const int N = 102;
#define mem(a,x) memset(a,x,sizeof(a))
#define fir(i,a,b) for(int i=a;i= mod) x -= mod;
}
void solve()
{
	cin>>n>>m;
	f[0][0][2] = 1;
	fir(i,0,n)
	{
		fir(j,0,m)
		{
			fir(k,0,m)
			{
				//翻倍
				if(k%2==0 && i)
				add(f[i][j][k],f[i-1][j][k/2]);
				if(j)
				add(f[i][j][k],f[i][j-1][k+1]);
			}
		}
	}
	cout