比赛链接

给定 $N,K$。要求将 $K$ 分解为 $N$ 个数，每个数均为 $1,\frac 12,\frac 14\cdots \frac 1{2^i}\cdots$询问分解方案数。

设 $\text{dp}(i,j)$ 表示需要将当前值分解为 $i$ 个数，且如果使用当前可以用的最大的数分解需要 $j$ 个的方案数。

于是假如使用一个当前可以用的最大的数，则有 $\text{dp}(i,j)\gets \text{dp}(i-1,j-1)$ 表示使用一个当前可以用的最大的数。

$\text{dp}(i,j)\gets \text{dp}(i,j<<1)$ 表示禁止使用当前可以用的最大的数。于是可以 $O(nk)$ 完成转移。

const int MAXN=3005,Mod=998244353;
int dp[MAXN][MAXN];
int dfs(int n,int k){
	if(k>n)return 0;
	if(n==0||k==0)return n==0&&k==0;
	if(~dp[n][k])return dp[n][k];
	return dp[n][k]=(dfs(n-1,k-1)+dfs(n,k<<1))%Mod;
}
int main()
{
	int n=read_int(),k=read_int();
	mem(dp,-1);
	enter(dfs(n,k));
	return 0;
}