一、题目
注意翻译中有两点没说到：(a_i) 不被 (k) 整除；(sum a_ileq 2000)
二、解法
不难写出 (O(3^nsum a_i)) 的子集枚举，但是显然 ( t T) 飞并且无法优化。
深究这样 (dp) 不行的原因：其实是插入的 (x+y) 需要立即除以 (k)，这导致我们难以判断某一状态的优劣，难以去除无效转移；并且这个转移具有强烈的顺序性，只能通过暴力 (dp) 考虑所有的组合方式。
被逼入绝境的我们只能找结论了，注意一定要找必要条件再证明其充分性（充分条件真的找不出来），思考本题顺序性是最大的难点，那么我们找的结论就一定要帮助我们逃离顺序性的桎梏。
考虑合法解中每个数，每个数被 (k) 除的次数是不同的，那么我们就考虑这个被除的次数 (b_i)，所有数被除以后加起来是 (1)，那么必要条件显然是存在一个非负 (b) 序列使得：(sum a_icdot k^{-b_i}=1)
然后考虑证明其充分性，也就是如果有 (b) 序列满足 (sum a_icdot k^{-b_i}=1) 能推出一组合法解，证明可以考虑归纳法，首先序列长为 (1/2) 时是对的，当序列长为 (n>2) 时，设 (alpha=max b_i)，如果两个 (alpha) 合并之后能被 (k) 整除，就能让 (b_i) 变小归纳下去，否则再和 (alpha) 合并， 因为分母是 (k^{alpha}) 而且最后求和是 (1)，所以不可能出现归纳不下去的情况，充分性得也。
根据这个结论设计 (dp)，不难发现现在我们要决策 (b) 序列，如果你看懂了证明就会发现大的 (b_i) 内部合并完之后要到更小的 (b_i) 才行，所以我们按 (b_i) 从大到小的顺序来 (dp)，但在实现中就把以前集合 (s) 中的 (b_i) 全部加 (1) 即可。
设 (dp[s][p]) 表示集合 (s) 的求和是 (p) 可不可行，转移：
- 向集合中加入 (b_i=0) 的一个 (a_i)：(dp[s|2^i][p+a_i]leftarrow dp[s][p])
- 把集合中的 (b_i) 全部增加 (1)：(dp[s][p]leftarrow dp[s][pcdot k])，这个要用完全背包的转移顺序。
不难发现可以用 ( t bitset) 优化，时间复杂度 (O(frac{1}{w}ncdot 2^ncdot sum a_i))
三、总结
找结论的小 ( t tirck)：考虑需要解决什么问题，找对应的结论；找必要性结论（充分性一般归纳证明）
决策具有某种性质的序列问题，用状压来定大小顺序，然后考虑整体加值。
#include <cstdio>
#include <bitset>
#include <iostream>
#include <queue>
using namespace std;
#define pii pair<int,int>
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,k,a[20],b[20];bitset<2005> dp[1<<16];
void dfs(int s,int p)
{
if(!s) return ;
if(p*k<=m && dp[s][p*k])
{
for(int i=0;i<n;i++)
if(s&(1<<i)) b[i+1]++;
dfs(s,p*k);
return ;
}
for(int i=0;i<n;i++)
if((s&(1<<i)) && a[i+1]<=p && dp[s^(1<<i)][p-a[i+1]])
{
dfs(s^(1<<i),p-a[i+1]);
return ;
}
}
signed main()
{
n=read();k=read();
dp[0][0]=1;
for(int i=1;i<=n;i++)
a[i]=read(),m+=a[i];
for(int s=1;s<(1<<n);s++)
{
for(int i=1;i<=n;i++)
if(s&(1<<i-1))
dp[s]|=dp[s^(1<<i-1)]<<a[i];
for(int i=m/k;i>=1;i--)//attention the order
dp[s][i]=dp[s][i]|dp[s][i*k];
}
if(!dp[(1<<n)-1][1])
{
puts("NO");
return 0;
}
puts("YES");
dfs((1<<n)-1,1);
priority_queue<pii> q;
for(int i=1;i<=n;i++)
q.push(make_pair(b[i],a[i]));
while(q.size()>=2)
{
pii t1=q.top();q.pop();
pii t2=q.top();q.pop();
printf("%d %d
",t1.second,t2.second);
int x=t1.second+t2.second,y=t1.first;
while(x%k==0 && y) y--,x/=k;
q.push(make_pair(y,x));
}
}