题解 | #货币 一种优美的动态规划做法

这里是N题的一种优美的动态规划做法，不需要任何额外知识，代码长度不超过1k。

先贴代码

#define ll long long
#define p 1000000007
using namespace std;
//fij,  2^i用最大不超过2^j表示的方案数（必选2^j） 
int f[65][35];
int dp[35],g[35];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	for(int i=0;i<=60;i++){
		f[i][0]=1;
		for(int j=1;j<=30&&j<=i;j++){
			for(int k=0;k<=j&&k+1<=i;k++)
			(f[i][j]+=1ll*f[i-1][k]*f[i-1-k][j-k]%p)%=p;
			if(i==j)f[i][j]++;
		}
	}
		
	int t;ll n;int m;
	cin>>t;
	while(t--){
		cin>>n>>m;m--;
		dp[0]=1;for(int i=1;i<=30;i++)dp[i]=0;
		for(int i=0;i<=60;i++)if(n>>i&1){
			for(int j=0;j<=30;j++)g[j]=dp[j],dp[j]=0;
			for(int k=min(i,m);k>=0;k--)
			for(int j=0;j<=k;j++)
			(dp[k]+=1ll*g[j]*f[i-j][k-j]%p)%=p;
		}
		int tot=0;
		for(int i=0;i<=m;i++)(tot+=dp[i])%=p;
		cout<<tot<<endl;
	}
	return 0;
}

原题可以转换成：由任意个组成的非降序列，满足和为n的序列数量。 设f[i][j]表示，由最大为(且必须包含）的数，拼出的方案数 可以证明，当j不等于i时，必然存在一个前缀和等于，因此可以简单理解为对两侧进行拼接。 后续的dp也用到了这一性质。具体证明可以私聊。