CF 1225G To Make 1（转化，状压DP，bitset）

直接按照题目的过程模拟是$O(n!)$的，$DP$是$O(3^n\Sigma a_i)$的。

考虑将题目的过程规约到另一个问题。

寻找一组解$b_i$使得$1={\sum }_i{a}_i{k}^{-b_i}$。

首先显然任意的一个可以得出1的合并过程都可以推出一组解$b_i$

证明：一定可以通过$b_i$构造出一组解。

先证明一个引理：当数字的数量$n>1$时一定有两个不相等的$j,k$满足$b_k=b_j=(\text{int}B={\max }_i{b}_i)$应该懂我的B什么意思吧

引理的证明：$1={\sum }_i{a}_i{k}^{-b_i}->k^B={\sum }_i{a}_i{k}^{B-b_i}$

这个等式两边的任意一项都是整数。

而左边被$k$整除，右边的所有的$b_i<B$的$a_i{k}^{B-b_i}$也被$k$整除

所以右边的所有的$b_i=B$的$a_i{k}^{B-b_i}$的和一定被$k$整除。

也就是说所有的$b_i=B$的$a_i$的和被$k$整除。

通过阅读英文版的输入格式我们可以发现不存在$k|a_i$。

所以$b_i=B$的$a_i$至少有两个。

所以对于一组$b_i$，我们取出$b_k=b_j=B$，

把$a_k$和$a_j$合并得到$a^{\prime }$

发现合并后依然满足不存在$k|a^{\prime }$

并且我们可以推出来合并出来的$a^{\prime }$它应该对应的$b^{\prime }$，把它们加入，就得到了一个规模为$n-1$的子问题，得到了一个$|b|=n-1$的$b_i$

而当$n=1$的时候我们就得到了$1$。

可以设计$d{p}_{s,u}=1$表示加入了$s$集合内的所有$a_i$后可以得到$u={\sum }_i{a}_i{k}^{-b_i}$

可以简单转移，但是会$TLE$,用$bitset$优化状态存储和转移即可$AC$.

$\mathrm{A}\mathrm{C}\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

#include<bits/stdc++.h> #define maxn 2005 #define pii pair<int,int> #define mp make_pair using namespace std; int n,k,a[16],lg[1<<16],N,sum; bitset<maxn> dp[1<<16]; int d[16]; priority_queue<pii >q; void dfs(int sta,int s){ if(!sta) return; for(;s*k<=sum && dp[sta][s*k];s*=k) for(int t=sta;t;t-=t&-t) d[lg[t&-t]]++; for(int t=sta;t;t-=t&-t) if(s>=a[lg[t&-t]] && dp[sta-(t&-t)][s-a[lg[t&-t]]]){ dfs(sta-(t&-t),s-a[lg[t&-t]]); return; } } int main(){ scanf("%d%d",&n,&k);N=1<<n; for(int i=0;i<n;i++) scanf("%d",&a[i]),lg[1<<i]=i,sum+=a[i]; dp[0][0] = 1; for(int i=1;i<N;i++){ for(int t=i;t;t-=t&-t){ int v=t&-t , u = lg[v]; dp[i] |= (dp[i-v]<<a[u]); } for(int j=sum/k;j>=1;j--) if(dp[i][j*k]) dp[i][j] = 1; } if(!dp[N-1][1]) puts("NO"); else{ puts("YES"); dfs(N-1,1); for(int i=0;i<n;i++) q.push(mp(d[i],a[i])); for(;q.size() > 1;){ pii u = q.top();q.pop(); pii v = q.top();q.pop(); printf("%d %d\n",u.second,v.second); u.second += v.second; for(;u.second % k == 0;u.second /= k) u.first --; q.push(u); } } }