1. Solution

首先有一个结论：

Theory 1

当 $m=n-1$ 的时候，一定存在合法方案。

proof

我们不妨将所有 $d_i$ 从小到大排序，显然不影响合法方案是否存在。
当 $n=2,m=1$ 的时候显然成立，现在我们考虑将这个结论推广。

Lemma 1.1

$d_1<k$

proof

如果 $d_1\ge k$，则 $\sum_{i=1}^n d_i\ge nd_1\ge nk>(n-1)k$，和条件不符。

Lemma 1.2

$\forall n>2,d_1+d_n>k$

proof

如果 $d_1+d_n\le k$，则 $d_n\le k-d_1\le k-1$，所以 $\sum_{i=2}^n d_i\le (n-1)(k-d_1)=(n-1)k-(n-1)d_1$，所以 $\sum_{i=1}^n d_i\le (n-1)k-(n-2)d_1< (n-1)k$，与条件不符。

所以，设 $n\le k$ 时命题成立，证明 $n=k+1$ 时成立，我们通过耗尽第一种原料并加入最后一种原料，可以转换为 $n=k$ 的命题，根据假设，是成立的。
根据数学归纳法，得到 $n\ge 2$ 时命题成立。
根据上面的做法模拟，利用 set 维护当前序列，可以做到 $\text{O}(n\log n)$ 的时间复杂度。

然后，我们发现另一个结论：

Theory 2

当 $m\ge n$ 的时候，一定存在合法方案。

proof

同样将所有 $d_i$ 从小到大排序，显然不影响合法方案是否存在。
我们考虑将问题转换为上面的形式，也即 $m=n-1$ 的情况。

Lemma 2.1

$d_n\ge k$

proof

显然成立，若 $d_n<k$，则 $\sum_{i=1}^n d_i\le nd_n<nk$，与条件冲突。

根据这个引理，我们可以取第 $n$ 种原材料 $k$ 克，直接做一道菜，此时 $m$ 减一，$n$ 至多减一，不停做，直到 $n=0$ 或 $m=n-1$ 即可。

Theory 3

当 $m=n-2$ 的时候，存在合法方案，当且仅当所有原材料可以被划分为两组，且每一组满足 $n=|S|，\sum_{i\in S} d_i=(n-1)k$。

proof

显然，直接合并两组的方案即可。

由此，我们对所有 $d_i-k$ 做零一背包，则条件就是存在和为 $-k$ 的方案，利用 bitset 优化即可做到 $\text{O}(\frac{n^2k}{\omega})$。

2. Code

/*by ChenMuJiu*/
/*略去缺省源和快读快写*/
const int N=505;
int n,m,k;
int d[N],idx[N];
namespace Subtask1{
#define pii pair<int,int>
set<pii>st;
void solve(int *d,int *idx,int n,int m){
	st.clear();
	for(int i=1;i<=n;i++)
		st.insert({d[i],idx[i]});
	while(n&&m>=n){
		auto it=*st.rbegin();
		st.erase(it);
		write(it.second),Spa,write(k),Nxt;
		it.first-=k,m--;
		if(it.first==0){
			n--;
			continue;
		}
		st.insert(it);
	}
	while(st.size()>=2){
		auto x=*st.rbegin(),y=*st.begin();
		st.erase(x),st.erase(y);
		write(y.second),Spa,write(y.first),Spa,write(x.second),Spa,write(k-y.first),Nxt;
		x.first-=k-y.first;
		st.insert(x);
	}
}
#undef pii
}
namespace Subtask2{
const int N=5e6+5;
bitset<N>f[505];
int tmpd[505],tmpidx[505];
void solve(){
	for(int i=0;i<=n;i++)
		f[i].reset();
	f[0][2500000]=1;
	for(int i=1;i<=n;i++){
		int x=d[i]-k;
		f[i]=f[i-1];
		if(x>=0)
			f[i]|=(f[i-1]<<x);
		else
			f[i]|=(f[i-1]>>-x);
	}
	if(!f[n][2500000-k]){
		puts("-1");
		return ;
	}
	vector<int>a,b;
	for(int i=n,S=2500000-k;i>=1;i--){
		if(f[i-1][S-(d[i]-k)]){
			a.push_back(i);
			S-=d[i]-k;
		}else b.push_back(i);
	}
	int cnt=0;
	for(auto tmp:a){
		cnt++;
		tmpd[cnt]=d[tmp];
		tmpidx[cnt]=tmp;
	}
	Subtask1::solve(tmpd,tmpidx,cnt,cnt-1);
	cnt=0;
	for(auto tmp:b){
		cnt++;
		tmpd[cnt]=d[tmp];
		tmpidx[cnt]=tmp;
	}
	Subtask1::solve(tmpd,tmpidx,cnt,cnt-1);
}
}
signed main(){
	int t;
	read(t);
	while(t--){
		read(n),read(m),read(k);
		for(int i=1;i<=n;i++)
			read(d[i]),idx[i]=i;
		if(m>=n-1)
			Subtask1::solve(d,idx,n,m);
		else Subtask2::solve();
	}
}

这篇题解将给出详细的证明。如果我能拿到自己考场代码应该会贴（不过看起来希望渺茫）。

看到题目感觉无从下手。观察数据范围，发现一个奇怪的限制 $n-2\leq m$，而且还专门给出了 $m=n-1$ 和 $m\geq n-1$ 的部分分，我们不妨从此入手思考。

对于 $m=n-1$，枚举 $n=2,3$ 发现都一定有解。我们不妨尝试直接将 $n$ 向 $n-1$ 转化：不失一般性，令 $d_1\leq d_2\leq \cdots\leq d_n$。我们发现应该要尽量先用光少的那些材料，而且少的尽量要配大的。可以证明下面两条引理：

引理一：$d_1 < k$。

证明： 用反证法。假设 $d_1\geq k$，那么 $d_2,...,d_n\geq k$，则 $d_1+\cdots+d_n\geq nk>(n-1)k=d_1+\cdots+d_n$。显然矛盾，故命题得证。

引理二：$d_1+d_n\geq k$。

证明： 用反证法。假设 $d_1+d_n\leq k-1$，那么 $d_n\leq k-1-d_1$，则 $d_1+d_2+\cdots+d_n\leq d_1+(n-1)(k-1-d_1)=(n-1)k-(n-1)-(n-2)d_1 < (n-1)k$，矛盾，所以 $d_1+d_n\geq k$。

综合上面两条引理，我们可以一次把 $d_1$ 用光，同时用 $d_n$ 填补空缺，显然是可行的。这样就成功将 $n$ 的情况转化成了 $n-1$ 的情况。而 $n=2$ 时直接放一起即可。综上，我们成功对于 $m=n-1$ 的任意情况构造出了一组解。

直接模拟的时间复杂度为 $O(n^2)$；可以简单用数据结构优化到 $O(n\log n)$，虽然本题中没有必要。

对于 $m\geq n$ 的情况，考虑向 $m=n-1$ 转化。同上令 $d_1\leq \cdots\leq d_n$，显然可证

引理三： $d_n\geq k$。

证明： 如果 $d_n < k$，则 $d_1+d_2+\cdots d_n < nk\leq mk=d_1+d_2+\cdots d_n$。矛盾。

所以我们用 $d_n$ 单独做一道菜，就可以令 $m$ 减少 $1$。这样就转化为 $m=n-1$ 的情况了。时间复杂度 $O(mn)$ 或 $O(m\log n)$。

接下来是最后的部分：$m=n-2$。

先手推一下 $n$ 较小的情况，发现 $n=3$ 必定无解，$n=4$ 是有解当且仅当存在两个 $d$ 加起来等于 $k$。也就是说，我们似乎要将这个问题向 $m=n-1$ 转化；把 $n$ 个物品分为两个集合，如果两个集合都能找到 $m=n-1$ 的方法，那么加起来就有一个 $m=n-2$ 的方法了。也就是说

引理四： 问题有解当且仅当能找到一个集合 $U=\{1,...,n\}$ 的子集 $S$，使得：

• 记 $x=|S|$ 为 $S$ 的大小，则 $\sum_{i\in S}d_i=(x-1)k$。

证明：

• 充分性： 显然对于集合 $S$ 和 $T=U-S$，都是一个满足 $m=n-1$ 的子问题，而我们已经证明过了 $m=n-1$ 必定有解，则对 $S,T$ 分别构造解即可。

• 必要性： 考虑构造一张图 $G$，$G$ 中有 $1,...,n$ 这些节点，如果两种原料在一道菜里同时选用则连一条边。发觉 $G$ 中至多有 $n-2$ 条边，则 $G$ 一定不连通。设 $G$ 有一个连通块 $S$，则相当于 $S$ 必须满足 $m=n-1$ 的有解约束，即 $\sum_{i\in S}d_i=(x-1)k$。证毕。

总之，只要我们能找到一些物品的集合 $S$ 满足 $\sum d=(|S|-1)k$，就能构造出符合题意的解。如何求这个 $S$ 呢？显然考虑做背包 DP。而由于右边带了一个 $|S|$，我们再做一步转化，将 $|S|k$ 移到左边，即要求

$\sum (d-k)=-k$

这样就变成一道经典的 01 背包问题了。直接求解的时间复杂度为 $O(n\sum d_i)=O(n^2k)$，用 bitset 优化即可做到 $O(\dfrac{n^2k}{w})$。

其他想说的话：

• 这题确实是一道锻炼思维的题，据我个人观察，考场上坐我旁边的选手们人均思考了一小时以上。
• 我大致想出了正解的思路，但没有想出 bitset 优化，前边 $n\leq 4$ 的特判又挂了（哈哈哈哈哈），感觉 $100->85$ 没什么，$85->70$ 确实是自己的水平问题……
• 希望以后 NOI 能多出今年这样的思维好题吧。