C、智乃买瓜(another version)

这道题属于是萌新也能做的多项式题（多项式除法）当然，解这道题不需要这么麻烦的理解啦。

看到题目之后很自然的逆向思维，既然这道题是原题输入输出的倒置。不妨去想，怎么把放进背包的物品取出来。

观察题目，说整只西瓜的质量都是偶数，那么最终答案为什么会出现质量和为奇数的情况？显然是由于有买半个瓜的决策。

那么就可以从小到大逆推，首先能够知道， $d p [1]$ 的值实际上就是质量为2的瓜的数目。

接下来的问题在意，已经知道了整个背包的信息（DP数组），如何把这些质量为2的瓜从背包中取出？

观察DP转移方程，是一个加法和式。

$dp[i][j]=dp[i-1][j-w_{i}]+dp[i-1][j-\frac{w_i}{2}]+dp[i-1][j]$

天然的逆向思维，怎么加上去的，就怎么减回来。

则有

$dp[i][j]-dp[i-1][j-w_{i}]-dp[i-1][j-\frac{w_i}{2}]=dp[i-1][j]$ （移项）

$dp[i-1][j]=dp[i][j]-dp[i-1][j-w_{i}]-dp[i-1][j-\frac{w_i}{2}]$

$dp[i][j]=dp[i+1][j]-dp[i][j-w_{i}]-dp[i][j-\frac{w_i}{2}]$ （令 $i = i + 1$ ，下标偏移1个单位）

这样，我们就得到了原题的逆动态规划转移方程，倒着来一遍还原即可，和上一道题一样，实际处理时习惯使用滚动数组优化到一维。

以下内容不太用关注(=-=)如果你对此没有疑问的话。

还有一个不太关键的问题：这道题的解是否唯一，显然是不唯一的，就算你胡乱生成一个 $a n s$ 数组，也总是能够得到一个有穷范围内可以表示的解（当然，也许很大，所以还需要一些卷积加速的手段），那如何保证std这样的方法不会超过限制？

换句话说这个题只讨论到这里是不够严谨的，如何证明std拿到的解，其西瓜数目是最少的？

这个题最小解唯一，因为从本质来讲，这道题就是让你将若干个形如 $(1+x^{w}+x^{\frac{w_i}{2}})^k$ 生成函数的积还原，并且你已知了每一步的 $w$ 以及 $k$ ，那么显然无论正着推还是反过来，步骤都是唯一的。

如果没懂的话，简单来讲，这道题就好像是现在有若干个数字，你不知它们都是几，但是你知道它们的乘积是X(比如a*b*c*d=X)，然后你可以通过一个固定操作知道乘积中最后一个数字是谁（而且保证这个数字是最小的），比如现在是d，所以你取出了d，然后令X=x/d，除完之后拿到了新的X，并且你继续通过这个操作知道现在里面最后一个乘进去的数字是c...然后进行若干轮重复操作后，你剩下一个X=1和a,b,c,d四个数字，所以说X是a,b,c,d四个数的乘积，并且这个过程是一个唯一过程。换句话说，最小解的唯一性是由于每一步拿取的数字唯一保证的。

如果不带模，那确实这样的最小解唯一，但是这里仍有不严谨的地方，由于模了 $1 0^{9} + 7$ ，那每次取得这个最小的数万一不是 $k$ 而是 $k + 1 0^{9} + 7$ 咋办？

显然是不可能的，因为这道题的西瓜数目最大才1000，所以这种情况被直接排除了。

这里给我们提供的启示是，如果不保证西瓜数目的最大值（1000）要求任意构造，你仍然可以用std的思路求解，但是在还原时要使用卷积加速的手段求解，当然，输出的格式要改成，输出西瓜的重量+这种重量西瓜的数目，这就是另外一道题了。

时间复杂度 $O (N M)$ ，空间复杂度 $O (N)$ 。

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
const int MAXN=1005;
long long dp[MAXN];
int m;
vector<int>ans;
int main()
{
	dp[0]=1;
	scanf("%d",&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%lld",&dp[i]);
	}
	for(int i=1;i<=m;++i)
	{
		while(dp[i])
		{
			ans.push_back(i*2);
			assert(ans.size()<=1000);
			for(int j=0;j<=m;++j)
			{
				if(j+i<=m)dp[j+i]-=dp[j];
				while(j+i<=m && dp[j+i]<0)dp[j+i]+=mod;
				if(j+i+i<=m)dp[j+i+i]-=dp[j];
				while(j+i+i<=m && dp[j+i+i]<0)dp[j+i+i]+=mod;
			}
		}
	}
	printf("%d\n",ans.size());
	for(int i=0;i<ans.size();++i)
	{
		printf("%d%c",ans[i]," \n"[i+1==ans.size()]);
	}
	return 0;
}

题解 | #智乃买瓜(another version)#

C、智乃买瓜(another version)