贪心策略：用一个map当做桶来用，然后从大到小遍历map
如果某个值出现次数是偶数，说明这个数可以被两边平分，
反之有一边就要多一个这个数，为了平衡，我们要在另一边补上缺少的值
补的方法：设少的值是x，那么此时大于x的数已经分配完成，剩下的数范围为[0,x-1]，我们只要枚举x-1到0，直到补完缺少的x
会出现补不完的情况，比如x在某个位置所需要的x-j的个数超过了1e6(显然补不完了)，或者枚举到0了还是补不完，这时候就可以算答案了
答案=|p^x-[0,x-1]范围内所有的和|
ps：少想了点细节，，fst了淦。。
#include<bits/stdc++.h> using namespace std; #define ll long long #define mod 1000000007 #define N 2000005 ll n,p,k[N]; vector<ll>s; map<ll,ll>mp,mp1; ll Pow(ll a,ll b){ ll res=1; while(b){ if(b%2)res=res*a%mod; b>>=1;a=a*a%mod; } return res; } int main(){ int t;cin>>t;int flag=0; for(int tt=1;tt<=t;tt++){ scanf("%lld%lld",&n,&p); for(int i=1;i<=n;i++)scanf("%lld",&k[i]); if(p==1){ if(n%2==0)cout<<0<<‘\n‘; else cout<<1<<‘\n‘;continue; } s.clear();mp.clear(); for(int i=1;i<=n;i++)mp[k[i]]++; for(auto p:mp)s.push_back(p.first); mp1=mp; int f=0; for(int i=s.size()-1;i>=0;i--)if(!f){ ll x=s[i]; ll need=1,dif=Pow(p,x); if(mp[x]%2!=0){ for(int j=1;j<=s[i];j++){ need*=p; if(mp[x-j]>=need){ mp[x-j]-=need; need=0; break; }else { need-=mp[x-j]; mp[x-j]=0; } if(need>1e12 || j==s[i]&&need)break; } if(need!=0){ for(int k=0;k<i;k++) dif=(dif-Pow(p,s[k])*mp1[s[k]]%mod+mod*2)%mod; cout<<dif<<‘\n‘; f=1; } } else continue; } if(!f)cout<<0<<‘\n‘; } }
原文：https://www.cnblogs.com/zsben991126/p/13047643.html